最短路径问题

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

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 #include <bits/stdc++.h>
 2 #define inf 0X3F3F3F3F
 3 using namespace std;
 4 
 5 #define INF 0X3F3F3F3F 
 6 struct Node{
 7     int val;
 8     int price;
 9 };
10 
11 Node mp[1010][1010];
12 int dis[1010], cost[1010], vis[1010];
13 
14 int n, m, x, y, k, z, s, t;
15 
16 void short_path(int a){
17     for(int i = 1; i <= n; i++){
18         dis[i] = mp[a][i].val;
19         cost[i] = mp[a][i].price;
20     }
21     memset(vis, 0, sizeof(vis));
22     dis[a] = 0;
23     cost[a] = 0;
24     vis[a] = 1;
25     for(int i = 1; i < n; i ++){
26         int u;
27         int mi = inf;
28         int va = inf;
29         for(int j = 1; j <= n; j++){
30             if(!vis[j] && dis[j] < mi){
31                 mi = dis[j];
32                 va = cost[j];
33                 u = j;
34             }else if(!vis[j] && dis[j] == mi && cost[j] < va){
35                 va = cost[j];
36                 u = j;
37             }
38         }
39         vis[u] = 1;
40         for(int j = 1; j <= n; j++){
41             if(mp[u][j].val < inf && !vis[j]){
42                 if(dis[j] > dis[u] + mp[u][j].val){
43                     dis[j] = dis[u] + mp[u][j].val;
44                     cost[j] = cost[u] + mp[u][j].price;
45                 }else if(dis[j] == dis[u] + mp[u][j].val){
46                     cost[j] = min(cost[j], cost[u] + mp[u][j].price);
47                 }
48             }
49         }
50     }
51 }
52 
53 
54 int main(){
55 
56     while(~scanf("%d%d", &n, &m) && (n || m)){
57         memset(mp,inf,sizeof(mp));
58         for(int i = 0; i < m; i ++){
59             scanf("%d%d%d%d", &x,&y,&k,&z);
60             if(mp[x][y].val > k){
61                 mp[x][y].val = mp[y][x].val = k;
62                 mp[x][y].price = mp[y][x].price = z;
63             }else if(mp[x][y].val == k){
64                 mp[x][y].price = mp[y][x].price = min(k,mp[x][y].price);
65             }
66         }
67         scanf("%d%d",&s,&t);
68         short_path(s);
69         printf("%d %d
", dis[t], cost[t]);
70     }
71     return 0;
72 }