当前位置：首页 > news >正文

杭电3790--最短路径问题（双权Dijkstra）

news 来源：原创 2024/5/3 19:08:45

最短路径问题

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

浙大计算机研究生复试上机考试-2010年

Recommend

notonlysuccess | We have carefully selected several similar problems for you: 2066 1217 2112 1142 1548

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

 1 #include <cstdio>
 2 #include <cstring>
 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<m; i++)
17     {
18         int min = INF, temp = cra;
19         for(j=1; j<=m; j++)
20         {
21             if(!vis[j] && dis1[j] < min)
22             {
23                 temp = j;
24                 min = dis1[j];
25             }
26         }
27         vis[temp] = 1;
28         for(j=1; j<=m; j++)
29         {
30             if(!vis[j] && dis1[j] > 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 }