最短路径问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 17425    Accepted Submission(s): 5199

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)

 

 

Output

输出 一行有两个数， 最短距离及其花费。

 

 

Sample Input

3 2

1 2 5 6

2 3 4 5

1 3

0 0

 

 

Sample Output

9

11

 

 

Source

 

 

Recommend

notonlysuccess   |   We have carefully selected several similar problems for you:            

RE: 题目中没有说花费钱也为最少， 所以距离和花费应是一一对应的；

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 const int INF = 0x3f3f3f; 5 int map[1010][1010], mpa[1010][1010], dis1[1010], dis2[1010], vis[1010]; 6 int i, j, m, n; 7 void Dijkstra(int cra) 8 { 9     memset(vis, 0, sizeof(vis));10     for(i=1; i<=m; i++)11     {12         dis1[i] = map[cra][i];13         dis2[i] = mpa[cra][i];14     }15     vis[cra] = 1;16     for(i=1; i
        
          dis1[temp] + map[temp][j])31             {32                 dis1[j] = dis1[temp] + map[temp][j];33                 dis2[j] = dis2[temp] + mpa[temp][j];34             }35             else if(!vis[j] && dis1[j] == dis1[temp] + map[temp][j] && dis2[j] > dis2[temp]+mpa[temp][j])36             {37                 dis2[j] = dis2[temp] + mpa[temp][j]; 38             }39         }40     }41 }42 int main()43 {44     while(~scanf("%d %d", &m, &n), m|n)45     {46         for(i=1; i<=m; i++)47         for(j=1; j<=m; j++)48         {49             map[i][j]=(i==j?0:INF);50             mpa[i][j]=(i==j?0:INF);51         }52         int a, b, d, p;53         for(i = 1; i <= n; i++)54         {55             scanf("%d %d %d %d", &a, &b, &d, &p);56         /*    if(map[a][b] > d)                     //坑。！ 57                 map[a][b]=map[b][a]=d;58             if(mpa[a][b] > p)59                 mpa[a][b]=mpa[b][a]=p;     */60             if(map[a][b] > d)61             {62                 map[a][b]=map[b][a]=d;63                 mpa[a][b]=mpa[b][a]=p;64             }65         }    66         int s, t;67         scanf("%d %d", &s, &t);68         Dijkstra(s);69         printf("%d %d\n", dis1[t], dis2[t]);70     }71     return 0;72 }