PAT1030

http://pat.zju.edu.cn/contests/pat-a-practise/1030

题目大意：求最短路径，并计算最短路径边权重之和，若最短路径不唯一，取边权重之和最小者。类似之前PAT的1018，不过比那个简单点，

用的是map<int, vector<pair<int, vector<int>>>> info; 来存储相应点的信息，每条最短路径的cost 以及最短路径所经过的结点（不包括自身）。

用的方法和之前1018基本一样。一个Dijkstra就够！

 1 #include<iostream>
 2 #include<vector>
 3 #include<utility>
 4 #include<map>
 5 #include<algorithm>
 6 using namespace std;
 7 #define INF 0x1fffffff
 8 
 9 bool comp(pair<int, vector<int>> p1, pair<int, vector<int>> p2)
10 {
11     if(p1.first < p2.first)
12         return true;
13     else
14         return false;
15 }
16 
17 void Dijkstra_version(vector<vector<int>> &tmap, vector<vector<int>> &cost, 
18                                 map<int, vector<pair<int, vector<int>>>> &info, vector<int> &dist, int S, int D)
19 {
20     dist[S] = 0;
21     vector<int> used(dist.size(), 0);
22     /*初始化起点*/
23     vector<int> v;
24     pair<int, vector<int>> p(0,v);
25     info[S].push_back(p);
26     while(S != D)
27     {
28         int kk(-1), min(INF);
29         for(int i=0; i<dist.size(); ++i)
30             if(used[i] == 0 && dist[i] < min)
31             {
32                 min = dist[i];
33                 kk = i;
34             }
35         used[kk] = 1;
36         for(int i=0; i<dist.size(); ++i)
37             if(used[i] == 0)
38                 if(tmap[kk][i] + dist[kk] < dist[i])
39                 {
40                     dist[i] = tmap[kk][i] + dist[kk];
41                     info[i] = info[kk];
42                     for(int j=0; j<info[i].size(); ++j)
43                     {
44                         /*更新cost*/
45                         info[i][j].first += cost[kk][i];
46                         /*将结点假如路径中*/
47                         info[i][j].second.push_back(kk);
48                     }
49                 }
50                 else if(tmap[kk][i] + dist[kk] == dist[i])
51                 {
52                     for(int j=0; j<info[kk].size(); ++j)
53                     {
54                         info[i].push_back(info[kk][j]);
55                         info[i][info[i].size()-1].first += cost[kk][i];
56                         info[i][info[i].size()-1].second.push_back(kk);
57                     }
58                 }
59         S = kk;
60     }            
61 }
62 
63 int main()
64 {
65     int N,M,S,D;
66     while(cin>>N>>M>>S>>D)
67     {
68         vector<int> colum(N, INF);
69         vector<vector<int>> tmap(N, colum);
70         vector<vector<int>> cost(N, colum);
71         for(int i=0; i<M; ++i)
72         {
73             int j,k,d,c; cin>>j>>k>>d>>c;
74             tmap[j][k]=tmap[k][j]=d;
75             cost[j][k]=cost[k][j]=c;
76         }
77         /*记录信息*/
78         map<int, vector<pair<int, vector<int>>>> info;
79         vector<int> dist(N, INF);
80         Dijkstra_version(tmap, cost, info, dist, S, D);
81         /*对所有最短路径按cost从小到大排序*/
82         sort(info[D].begin(), info[D].end(), comp);
83         for(int i=0; i<info[D][0].second.size(); ++i)
84             cout<<info[D][0].second[i]<<" ";
85         cout<<D<<" "<<dist[D]<<" "<<info[D][0].first<<endl;
86     }
87 }