最短路径问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8231 Accepted Submission(s): 2461
Problem Description
给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
Input
输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
(1<n<=1000, 0<m<100000, s != t)
Output
输出 一行有两个数, 最短距离及其花费。
Sample Input
3 2 1 2 5 6 2 3 4 5 1 3 0 0
Sample Output
9 11
#include <stdio.h> #define INF 0x7fffffff #define MAX 1002 struct node { int len,val; }map[MAX][MAX]; int dist[MAX],visited[MAX],cost[MAX]; void Dijkstra(int s,int t,int n) { int i,j,min,u; for (i=1;i<=n;i++) { dist[i]=map[s][i].len; cost[i]=map[s][i].val; visited[i]=0; } visited[s]=1; dist[s]=0; cost[s]=0; for (i=1;i<n;i++) { min=INF; u=i; for(j=1;j<=n;j++) if (!visited[j]&&dist[j]<min) { min=dist[j]; u=j; } visited[u]=1; for(j=1;j<=n;j++) { if (!visited[j]&&map[u][j].len<INF) { if(dist[j]>(map[u][j].len+dist[u])) { dist[j]=map[u][j].len+dist[u]; cost[j]=map[u][j].val+cost[u]; } else if(dist[j]==(map[u][j].len+dist[u])) { if(cost[j]>(map[u][j].val+cost[u])) cost[j]=map[u][j].val+cost[u]; } }//if }//for }//for printf("%d %d\n",dist[t],cost[t]); } int main() { int n,m,i,j,d,p,s,t; while(scanf("%d %d",&n,&m)&&n) { for (i=1;i<=n;i++) { for(j=1;j<=n;j++) { map[i][j].len=INF; map[i][j].val=INF; } } while(m--) { scanf("%d %d %d %d",&i,&j,&d,&p); if(map[i][j].len>d) { map[i][j].len=map[j][i].len=d; map[i][j].val=map[j][i].val=p; } else if(map[i][j].len==d) if(map[i][j].val>p) map[i][j].val=map[j][i].val=p; } scanf("%d %d",&s,&t); Dijkstra(s,t,n); } return 0; }