1 #include <vector>  2 #include <string>  3 #include <iostream>  4 #include <map>  5 #include <fstream>  6   7 //#define OJ  8   9 #ifdef OJ 10 #define fin cin 11 #endif 12  13 using namespace std; 14  15 class city{ 16 public: 17     int happiness; 18     string name; 19      20     vector<int> adj; 21     vector<int> cost; 22 }; 23  24 vector<city> cities; 25 map<string, int> city_idx; 26 map<int, string> city_name; 27  28 void dij(){ 29     int total = cities.size(); 30     int MAX = 0x7fffffff; 31  32     vector<bool> visited(total, false); 33     vector<int> dij_dist(total, MAX); 34     vector<int> dij_happiness(total, 0); 35     vector<int> prev(total, -1); 36     vector<int> dij_cnt(total, MAX); 37     vector<int> dij_least_cnt(total, 0); 38  39     int target_idx = city_idx["ROM"]; 40  41     dij_dist[0] = 0; 42     dij_cnt[0] = 0; 43     dij_least_cnt[0] = 1; 44  45     while (true){ 46         int least_dist = MAX; 47         int least_idx = -1; 48  49         for (int i = 0; i < total; i++){ 50             if (!visited[i] && least_dist > dij_dist[i]){ 51                 least_idx = i; 52                 least_dist = dij_dist[i]; 53             } 54         } 55  56         if (least_idx == -1) 57             break; 58         if (least_idx == target_idx) // ? 59             break; 60  61         visited[least_idx] = true; 62         vector<int> &adj = cities[least_idx].adj; 63         vector<int> &cost = cities[least_idx].cost; 64         for (int i = 0; i < adj.size(); i++){ 65             int cur_idx = adj[i]; 66             if (visited[cur_idx]) 67                 continue; 68             if (least_dist + cost[i] < dij_dist[cur_idx]){ 69                 dij_dist[cur_idx] = least_dist + cost[i]; 70                 prev[cur_idx] = least_idx; 71                 dij_cnt[cur_idx] = dij_cnt[least_idx] + 1; 72                 dij_happiness[cur_idx] = dij_happiness[least_idx] + cities[cur_idx].happiness; 73                 dij_least_cnt[cur_idx] = dij_least_cnt[least_idx]; 74             } 75             else if (least_dist + cost[i] == dij_dist[cur_idx]){ 76                 dij_least_cnt[cur_idx] += dij_least_cnt[least_idx]; 77  78                 if (dij_happiness[least_idx] + cities[cur_idx].happiness > dij_happiness[cur_idx]){ 79                     prev[cur_idx] = least_idx; 80                     dij_cnt[cur_idx] = dij_cnt[least_idx] + 1; 81                     dij_happiness[cur_idx] = dij_happiness[least_idx] + cities[cur_idx].happiness; 82                 } 83                 else if (dij_happiness[least_idx] + cities[cur_idx].happiness == dij_happiness[cur_idx]){ 84                     if (dij_cnt[least_idx] + 1 < dij_cnt[cur_idx]){ 85                         prev[cur_idx] = least_idx; 86                         dij_cnt[cur_idx] = dij_cnt[least_idx] + 1; 87                     } 88                 } 89             } 90         } 91     } 92  93     int idx = target_idx; 94     cout << dij_least_cnt[target_idx] << " " << dij_dist[target_idx] << " " << dij_happiness[target_idx] << " " << (int)(dij_happiness[target_idx] / dij_cnt[target_idx]) << endl; 95      96     vector<int> res; 97      98     while (idx != 0){ 99         res.push_back(idx);100         idx = prev[idx];101     }102     cout << city_name[0];103     for (int i = res.size() - 1; i >= 0; i--)104         cout << "->" << city_name[res[i]];105     cout << endl;106 }107 108 int main(){109 #ifndef OJ110     ifstream fin;111     fin.open("in.data");112 #endif113 114 115     int N, K;116     fin >> N >> K;117 118     string name;119     fin >> name;120     city_idx[name] = 0;121     city_name[0] = name;122 123     city c;124     c.name = name;125     c.happiness = 0;126 127     cities.push_back(c);128 129     for (int i = 1; i < N; i++){130         fin >> c.name;131         fin >> c.happiness;132 133         cities.push_back(c);134 135         city_name[i] = c.name;136         city_idx[c.name] = i;137     }138 139     for (int i = 0; i < K; i++){140         int c1, c2, cost;141 142         fin >> name;143         c1 = city_idx[name];144 145         fin >> name;146         c2 = city_idx[name];147 148         fin >> cost;149 150         cities[c1].adj.push_back(c2);151         cities[c1].cost.push_back(cost);152         cities[c2].adj.push_back(c1);153         cities[c2].cost.push_back(cost);154     }155 156     dij();157 158     return 0;159 }