时间限制：1 秒
内存限制：32 兆
特殊判题： 否
提交：62
解决： 28
标签
- 最短路径
题目描述
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
输入格式
输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
输出
输出 一行有两个数， 最短距离及其花费。
样例输入
3 2
1 2 5 6
2 3 4 5
1 3
0 0
样例输出
9 11
提示[+]
*** 提示已隐藏，点击上方 [+] 可显示 ***
分类
- 浙江大学研究生复试上机真题
- max min 在OJ c++都是保留字 函数名，在6.0里面可以编译通过，但是OJ上就不行!!!
-
1 #include<iostream> 2 #include<string> 3 using namespace std; 4 const int inf=10000000; 5 struct graph //节点 6 { 7 int len; 8 int cost; 9 }g[1001][1001],min1[1001];//g为图的连接矩阵，min存起点到个个点的最短距离和最少花费 10 void dijkstr(int n,int s)//n 节点个数 ，s起点编号 11 { 12 //初始化 13 int v[1001]={0};//v[i]=0 表示还没并入路径中； 14 for(int j=1;j<=n;j++) 15 { 16 min1[j].len=inf; 17 min1[j].cost=inf; 18 } 19 min1[s].len=0; 20 min1[s].cost=0; 21 for(int x=1;x<=n;x++) 22 { 23 int MIN=inf;//最小路长 24 int pri=inf;//最小费用 25 int u; 26 for(int y=1;y<=n;y++)//选最小的节点并入 27 { 28 if(v[y]==0&&((MIN>min1[y].len)||(MIN==min1[y].len&&pri>min1[y].cost))) 29 { 30 u=y; 31 MIN=min1[y].len; 32 pri=min1[y].cost; 33 } 34 } 35 v[u]=1; 36 for(int z=1;z<=n;z++) //更新u并入后的个个min的值 37 { 38 if(v[z]==0&&((min1[u].len+g[u][z].len<min1[z].len)||((min1[u].len+g[u][z].len==min1[z].len)&&(min1[u].cost+g[u][z].cost<min1[z].cost)))) 39 { 40 min1[z].len=min1[u].len+g[u][z].len; 41 min1[z].cost=min1[u].cost+g[u][z].cost; 42 } 43 } 44 } 45 } 46 int main() 47 { 48 int n; 49 while(cin>>n) 50 { 51 //初始化 52 for(int j=1;j<=n;j++) 53 for(int k=1;k<=n;k++) 54 { 55 g[j][k].len=inf; 56 g[k][j].cost=inf; 57 } 58 int m; 59 cin>>m; 60 if(n==0&&m==0) break; 61 for(int i=1;i<=m;i++) 62 { 63 int a,b,d,p; 64 cin>>a>>b>>d>>p; 65 g[a][b].len=d; 66 g[a][b].cost=p; 67 g[b][a].len=d; 68 g[b][a].cost=p; 69 } 70 int s,t; 71 cin>>s>>t; 72 dijkstr(n,s); 73 cout<<min1[t].len<<" "<<min1[t].cost<<endl; 74 } 75 return 0; 76 } 77