1 #include <cstdio>  2 #include <climits>  3 #include <iostream>  4 #include <vector>  5 #include <string>  6 #include <queue>  7 #include <unordered_map>  8 #include <algorithm>  9  10 using namespace std; 11  12 typedef pair<int, int> P; 13  14 class City { 15 public: 16     int        id; 17     string     name; 18     int     happiness; 19     int     distance; 20     vector<int> adj; 21     City(string _name, int _happiness = 0, int _id = 0, int _distance = INT_MAX) : 22         name(_name), happiness(_happiness), id(_id), distance(_distance) {} 23 }; 24  25 class Solution { 26 public: 27     int happiness; 28     vector<int> path; 29     Solution(int happy = 0) : happiness(happy) {} 30 }; 31  32 bool solution_cmp_inv(const Solution& a, const Solution& b) { 33     if (a.happiness > b.happiness) { 34         return true; 35     } else if (a.happiness < b.happiness) { 36         return false; 37     } else { 38         return a.happiness / a.path.size() > b.happiness / b.path.size(); 39     } 40 } 41  42 int G[200][200]; 43  44 vector<Solution> res; 45  46 void build_solution(vector<City*> &cities, Solution &s, int pos, int dst, int hap) { 47     // we know that start city index must be zero 48     // so when pos == 0, we get a solution 49     if (pos == 0) { 50         res.push_back(s); 51         res.back().happiness= hap; 52         return; 53     } 54      55     // we are now at the cities[pos] with left dst to the start city 56     City* city = cities[pos]; 57     for (int i=0; i<city->adj.size(); i++) { 58         City* adj = cities[city->adj[i]]; 59          60         // we could not go to this adj city, not on the shortest path 61         if (adj->distance + G[pos][adj->id] != dst) { 62             continue; 63         } 64          65         // here we can assume that the adj city is on the shortest path 66         s.path.push_back(adj->id); 67         build_solution(cities, s, adj->id, adj->distance, hap + adj->happiness); 68         s.path.pop_back(); 69     } 70 } 71 int main() { 72     vector<City*> cities; 73      74     unordered_map<string, int> city_lookup; 75      76     int        N, K; 77     char    buf[10], buf2[10]; 78      79     scanf("%d%d%s", &N, &K, buf); 80      81     City* start = new City(buf, 0, 0, 0); 82     cities.push_back(start); 83     city_lookup.insert(make_pair(start->name, 0)); 84      85     int tmp = 0; 86     for (int i=1; i<N; i++) { 87         scanf("%s%d", buf, &tmp); 88         cities.push_back(new City(buf, tmp, cities.size())); 89         city_lookup.insert(make_pair(buf, cities.back()->id)); 90     } 91      92     tmp = 0; 93     int ca = 0, cb = 0; 94      95     for (int i=0; i<K; i++) { 96         scanf("%s%s%d", buf, buf2, &tmp); 97          98         ca = city_lookup.find(buf)->second; 99         cb = city_lookup.find(buf2)->second;100         101         cities[ca]->adj.push_back(cb);102         cities[cb]->adj.push_back(ca);103         104         G[ca][cb] = G[cb][ca] =tmp;105     }106     107     priority_queue<P, vector<P>, greater<P>> cand_cities;108     cand_cities.push(make_pair(0, 0));109     110     while(!cand_cities.empty()) {111         P p = cand_cities.top();112         cand_cities.pop();113         114         City* sel_city = cities[p.second];115         116         if (sel_city->distance < p.first) continue;117 118         for (int i=0; i<sel_city->adj.size(); i++) {119             City* adj_city = cities[sel_city->adj[i]];120             121             int new_dst = sel_city->distance + G[sel_city->id][adj_city->id];122             123             if (adj_city->distance > new_dst) {124                 adj_city->distance = new_dst;125                 cand_cities.push(make_pair(new_dst, adj_city->id));126             }127         }128     }129     130     City* rom = cities[city_lookup.find("ROM")->second];131     132     Solution s;133     134     build_solution(cities, s, rom->id, rom->distance, rom->happiness);135     136     sort(res.begin(), res.end(), solution_cmp_inv);137     138     Solution& best = res[0];139     140     printf("%d %d %d %d\n", res.size(), rom->distance, best.happiness, best.happiness / best.path.size());141     142     for (int i = best.path.size() - 1; i>=0; i--) {143         printf("%s->", cities[best.path[i]]->name.c_str());144     }145     printf("ROM\n");146     return 0;147 }