AOJ 1318 - Long Distance Taxi

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

概要

自動車でガソリンを切らさずに出発地から目的地まで行きたい． その自動車は1リットルのガソリンで 10km 走ることができ，最大で cap リットルのガソリンを載せることができる．

N 本の距離 d[i] の道が街同士を双方向に結んでいる．

M 個の街にはガソリンスタンドがあり，そこでコスト無しで好きなだけ給油できる．

出発地から目的地までの最小の道程を答える．ただし，目的地まで行けない場合は -1 を答える．

制約

解法

ガソリンスタンドのある街で最大まで給油できるため，cap リットルのガソリンで到達できる街同士にエッジを張ったグラフを M 回ダイクストラして作り，そのグラフの上で普通にダイクストラして最短経路を求める．

  1 #include <iostream>
  2 #include <vector>
  3 #include <map>
  4 #include <queue>
  5 using namespace std;
  6 
  7 int main()
  8 {
  9   int N, M, C;
 10   while (cin >> N >> M >> C && N != 0) {
 11     C *= 10;
 12     map<string,int> m;
 13     string start, goal;
 14     cin >> start >> goal;
 15     m.insert(make_pair(start, 0));
 16     m.insert(make_pair(goal, 1));
 17     vector<vector<pair<int,int> > > gg(2);
 18     for (int i = 0; i < N; i++) {
 19       string src, dst;
 20       int d;
 21       cin >> src >> dst >> d;
 22       int u, v;
 23       if (!m.count(src)) {
 24         u = m.size();
 25         m.insert(make_pair(src, u));
 26         gg.push_back(vector<pair<int,int> >());
 27       } else {
 28         u = m[src];
 29       }
 30       if (!m.count(dst)) {
 31         v = m.size();
 32         m.insert(make_pair(dst, v));
 33         gg.push_back(vector<pair<int,int> >());
 34       } else {
 35         v = m[dst];
 36       }
 37       gg[u].push_back(make_pair(v, d));
 38       gg[v].push_back(make_pair(u, d));
 39     }
 40 
 41     vector<int> gss, gss_map(gg.size(), -1);
 42     gss.push_back(0); // start
 43     gss.push_back(1); // goal
 44     gss_map[0] = 0;
 45     gss_map[1] = 1;
 46     for (int i = 0; i < M; i++) {
 47       string s;
 48       cin >> s;
 49       const int v = m[s];
 50       if (v != 0 && v != 1) {
 51         gss_map[v] = gss.size();
 52         gss.push_back(v);
 53       }
 54     }
 55     const int MM = gss.size();
 56 
 57     static const int INF = 10000000;
 58     vector<vector<int> > dist(MM, vector<int>(MM, INF));
 59     for (int i = 0; i < MM; i++) {
 60       priority_queue<pair<int,int> > q;
 61       vector<int> dp(gg.size(), INF);
 62       dp[gss[i]] = 0;
 63       q.push(make_pair(0, gss[i]));
 64       while (!q.empty()) {
 65         const int n = q.top().second;
 66         const int c = -q.top().first;
 67         q.pop();
 68         if (c > dp[n]) {
 69           continue;
 70         }
 71         for (vector<pair<int,int> >::const_iterator it = gg[n].begin(); it != gg[n].end(); ++it) {
 72           int k = it->first;
 73           const int cc = c + it->second;
 74           if (cc <= C && cc < dp[k]) {
 75             dp[k] = cc;
 76             if (gss_map[k] != -1) {
 77               dist[i][gss_map[k]] = min(dist[i][gss_map[k]], cc);
 78             } else {
 79               q.push(make_pair(-cc, k));
 80             }
 81           }
 82         }
 83       }
 84     }
 85 
 86     priority_queue<pair<int,int> > q;
 87     vector<int> dp(MM, INF);
 88     dp[0] = 0;
 89     q.push(make_pair(0, 0));
 90     while (!q.empty()) {
 91       const int n = q.top().second;
 92       const int c = -q.top().first;
 93       q.pop();
 94       if (n == 1) {
 95         cout << c << endl;
 96         goto NEXT;
 97       }
 98       for (int v = 0; v < MM; v++) {
 99         const int cc = c + dist[n][v];
100         if (dist[n][v] != INF && cc < dp[v]) {
101           dp[v] = cc;
102           q.push(make_pair(-cc, v));
103         }
104       }
105     }
106     cout << "-1" << endl;
107 NEXT:
108     ;
109   }
110   return 0;
111 }
aoj/1318.cc