HDU3790

最短路径问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 23797 Accepted Submission(s): 7091

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

 1 //2016.4.21
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 const int maxn = 1005;
 9 const int inf = 9999999;
10 int Tu_dist[maxn][maxn], Tu_pay[maxn][maxn], dis[maxn], pay[maxn], book[maxn];
11 int n, m;
12 void dijkstra(int s);
13 
14 int main()
15 {
16     while(cin>>n>>m&&n&&m)
17     {
18         for(int i = 0; i <= n; i++)
19             for(int j = 0; j <= n; j++)
20             {
21                 Tu_dist[i][j] =inf;
22                 Tu_pay[i][j] = inf;
23             }
24 
25         int a, b, d, p, s, t;
26         while(m--)
27         {
28             scanf("%d%d%d%d", &a, &b, &d, &p);
29             if(d<Tu_dist[a][b])
30             {
31                 Tu_dist[a][b] = Tu_dist[b][a] = d;
32                 Tu_pay[a][b] = Tu_pay[b][a] = p;
33             }
34         }
35         scanf("%d%d", &s, &t);
36 
37         dijkstra(s);
38         printf("%d %d
", dis[t], pay[t]);
39     }
40     return 0;
41 }
42 
43 void dijkstra(int s)
44 {
45     int mindist, u, v;
46     for(int i = 1; i <= n; i++)
47     {
48         dis[i] = Tu_dist[s][i];
49         pay[i] = Tu_pay[s][i];
50     }
51 
52     memset(book, 0, sizeof(book));
53     book[s] = 1;
54     dis[s] = 0;
55     pay[s] = 0;
56 
57     for(int i = 1; i < n; i++)
58     {
59         mindist = inf;
60         for(int j = 1; j <= n; j++)
61         {
62             if(book[j]==0&&dis[j]<mindist)
63             {
64                 mindist = dis[j];
65                 u = j;
66             }
67         }
68         book[u] = 1;
69         for(int v = 1; v <= n; v++)
70         {
71             if(!book[v] && Tu_dist[u][v]<inf)
72             {
73                 if(dis[v]>dis[u]+Tu_dist[u][v])
74                 {
75                     dis[v] = dis[u]+Tu_dist[u][v];
76                     pay[v] = pay[u]+Tu_pay[u][v];
77                 }
78                 else if(dis[v]==(dis[u]+Tu_dist[u][v]))
79                     pay[v] = (pay[u]+Tu_pay[u][v])<pay[v]?pay[u]+Tu_pay[u][v]:pay[v];
80             }
81         }
82     }
83 }