HDU 3790--最短路问题(Dijkstra)

本文主要是介绍HDU 3790--最短路问题(Dijkstra)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3790
题意：
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
规模(1< n<=1000, 0< m<100000 )
类型：
最短路问题(Dijkstra)
分析：
这道题是在最基础的Dijkstra最短路上添了一个维度（花费），花费这里同“最短路程”相同，（在最短路前提下）只需要记录最小花费进行更新就好了。
TLE的可以试着改cin为scanf;
注意重边的情况
时间复杂度&&优化：
n^2
代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<algorithm>
#include<iostream>using namespace std;const int MAXN = 1005;
const int MAXM = 100005;
const int inf = 1000000007;
const int mod = 1000000007;int n,m;
int s,t;
struct LOAD{int length;int weight;
};LOAD load[MAXN][MAXN];
LOAD lowcost[MAXN];bool vis[MAXN];
void Dijkstra(LOAD cost[][MAXN],LOAD lowcost[],int n){for(int i=0;i<n;i++){vis[i]=false;lowcost[i].length=inf;lowcost[i].weight=inf;}lowcost[s].length=0;lowcost[s].weight=0;for(int j=0;j<n;j++){//找现在离源点最近的点int Min=inf;int k=-1;//为了跳出负边for(int i=0;i<n;i++){if(!vis[i]&&lowcost[i].length<Min){k=i;Min=lowcost[i].length;}}if(k==-1)break;//为了跳出负边//endvis[k]=true;for(int i=0;i<n;i++){if(!vis[i]&&lowcost[k].length+load[k][i].length<=lowcost[i].length){if(lowcost[k].length+load[k][i].length==lowcost[i].length){lowcost[i].weight=min(lowcost[k].weight+load[k][i].weight,lowcost[i].weight);}else lowcost[i].weight=lowcost[k].weight+load[k][i].weight;lowcost[i].length=lowcost[k].length+load[k][i].length;}}}
}int main()
{while(cin>>n>>m && (n||m)){for(int i=0;i<n;i++){for(int j=0;j<n;j++)load[i][j].length=load[i][j].weight=inf;}for(int i=0;i<m;i++){int z1,z2,z3,z4;scanf("%d%d%d%d",&z1,&z2,&z3,&z4);z1--;z2--;if(z3>load[z1][z2].length){continue;}else if(z3==load[z1][z2].length) z4=min(z4,load[z1][z2].weight);///注意重边load[z1][z2].length=load[z2][z1].length=z3;load[z1][z2].weight=load[z2][z1].weight=z4;}cin>>s>>t;s--;t--;Dijkstra(load,lowcost,n);cout<<lowcost[t].length<<" "<<lowcost[t].weight<<endl;}return 0;
}