AOJ 2283 - Seishun 18 Kippu

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2283

解法

2回ダイクストラするだけ．

 1 #include <iostream>
 2 #include <vector>
 3 #include <map>
 4 #include <queue>
 5 using namespace std;
 6 
 7 int numbering(map<string,int>& m, const string& s)
 8 {
 9   const map<string,int>::const_iterator it = m.find(s);
10   if (it == m.end()) {
11     const int n = m.size();
12     m.insert(make_pair(s, n));
13     return n;
14   } else {
15     return it->second;
16   }
17 }
18 
19 int dijkstra(const vector<vector<pair<int,int> > >& g, int start, int goal)
20 {
21   priority_queue<pair<int,int> > q;
22   vector<int> dist(g.size(), 10000000);
23   q.push(make_pair(0, start));
24   dist[start] = 0;
25   while (!q.empty()) {
26     const int c = -q.top().first;
27     const int n = q.top().second;
28     q.pop();
29     if (n == goal) {
30       return c;
31     }
32     if (dist[n] < c) {
33       continue;
34     }
35     for (vector<pair<int,int> >::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
36       const int cc = c + it->second;
37       if (cc < dist[it->first]) {
38         dist[it->first] = cc;
39         q.push(make_pair(-cc, it->first));
40       }
41     }
42   }
43   throw "fail";
44 }
45 
46 int main()
47 {
48   int N, M;
49   while (cin >> N >> M && N != 0) {
50     map<string,int> m;
51     string s, p, q;
52     cin >> s >> p >> q;
53     const int ss = numbering(m, s);
54     const int pp = numbering(m, p);
55     const int qq = numbering(m, q);
56     vector<vector<pair<int,int> > > g(N);
57     for (int i = 0; i < M; i++) {
58       string u, v;
59       int d, t;
60       cin >> u >> v >> d >> t;
61       const int c = d/40+t;
62       const int uu = numbering(m, u);
63       const int vv = numbering(m, v);
64       g[uu].push_back(make_pair(vv, c));
65       g[vv].push_back(make_pair(uu, c));
66     }
67     cout << dijkstra(g, ss, pp) + dijkstra(g, pp, qq) << endl;
68   }
69   return 0;
70 }