九度OJ1008

这道题其实就是一个简单的Dijkstra变形，只是要考虑重边的情况。

当在更新图中点到起点的距离时，将花费p也计算在内；如果长度与之前计算的值相等，则再考虑此时花费p是否会更少，是的话则仍然要更新最短路径。

我一开始想的是跑一遍迪杰斯特拉，记录下最短路的重边，然后再根据重边构建一个新的图，图中的权值则是花费p，再以此跑一遍Dijkstra，则就能得到题目要求的情况。这样理论上能做，但实现起来很麻烦，不如上面提到的简单。

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <vector>
 4 #include<string.h>
 5 #define INF 1<<30
 6 using std::vector;
 7 int n,m,graph[2][1001][1001],s,t,D[1001],P[1001];
 8 bool visited[1001];
 9 //vector<int> p[1001];
10 void Dijkstra()
11 {
12     int i,j;
13     //visited[s]=1;
14     for(i=1;i<=n;i++)
15     {
16         D[i]=INF;
17         P[i]=INF;
18     }
19     P[s]=0;
20     D[s]=0;
21     for(j=1;j<=n;j++)
22     {
23         int min=INF;
24         int k=-1;
25         for(i=1;i<=n;i++)
26         {
27             if(visited[i]==0&&min>D[i])
28             {
29                 min=D[i];
30                 k=i;
31             }
32         }
33         if(k!=-1)
34         {
35             visited[k]=1;
36             for(i=1;i<=n;i++)
37             {
38                 if(visited[i]==0&&D[i]>=D[k]+graph[0][k][i])
39                 {
40                     if(D[i]>D[k]+graph[0][k][i])
41                     {
42                         D[i]=D[k]+graph[0][k][i];
43                         P[i]=P[k]+graph[1][k][i];
44                         //printf("%d %d %d
",i,D[type][i],P[i]);
45                     }
46                     else if(D[i]==D[k]+graph[0][k][i]&&P[i]>P[k]+graph[1][k][i])
47                     {
48                         P[i]=P[k]+graph[1][k][i];
49                     }
50 
51                 }
52             }
53         }
54     }
55 }
56 int main()
57 {
58     int i,j;
59     //printf("%d
",INF);
60     scanf("%d%d",&n,&m);
61     while(!(n==0&&m==0))
62     {
63         int a,d,b,p1;
64         memset(visited,0,sizeof(visited));
65         for(i=1;i<=n;i++)
66         for(j=1;j<=n;j++)
67         {
68             if(i==j)
69             {
70             graph[0][i][j]=0;
71             graph[1][i][j]=0;
72             }
73             else
74             {
75             graph[0][i][j]=INF;
76             graph[1][i][j]=INF;
77             }
78         }
79         for(i=1;i<=m;i++)
80         {
81             scanf("%d%d%d%d",&a,&b,&d,&p1);
82             graph[0][a][b]=d;
83             graph[0][b][a]=d;
84             graph[1][a][b]=p1;
85             graph[1][b][a]=p1;
86         }
87         scanf("%d%d",&s,&t);
88         Dijkstra();
89         printf("%d %d
",D[t],P[t]);
90         scanf("%d%d",&n,&m);
91     }
92     return 0;
93 }