AOJ1318 long distance taxi

問題ページ
Long Distance Taxi | Aizu Online Judge

解法

拡張dijkstraをする。ガソリン量を10倍して1km/Lと考えると楽。
d[都市][残っているガソリン量] としてdijkstraをする。頂点がO(都市数*ガソリン量)で遷移がO(都市数)なので解ける。

入力が面倒だったり10km/Lだったり面倒だけど典型的な拡張dijkstra

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

vector<PII> g[6010];
int d[6010][2010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n, m, cap;
    cin >> n >> m >> cap; cap *= 10;
    if(!n) break;
    string src, dst;
    cin >> src >> dst;
    int V = 0;
    map<string,int> mp;
    REP(i, 6010) g[i].clear();
    REP(i, n) {
      int l;
      string s, t;
      cin >> s >> t >> l;
      if(mp.find(s) == mp.end()) {
        mp[s] = V++;
      }
      if(mp.find(t) == mp.end()) {
        mp[t] = V++;
      }
      g[mp[s]].PB({mp[t], l});
      g[mp[t]].PB({mp[s], l});
      // cout << mp[s] << " " << mp[t] << " " << l << endl;
    }
    VI exist(V, 0);
    REP(i, m) {
      string s;
      cin >> s;
      exist[mp[s]] = 1;
    }
    int start = mp[src], goal = mp[dst];
    // cout << V << endl;

    REP(i, V) REP(j, cap+1) d[i][j] = LLINF;
    d[start][cap] = 0;
    priority_queue<VI, VVI, greater<VI>> que;
    que.push({d[start][cap], start, cap});

    while(que.size()) {
      VI v = que.top(); que.pop();
      // cout << v << endl;
      int dist = v[0], place = v[1], gas = v[2];
      if(dist > d[place][gas]) continue;
      for(PII &p: g[place]) {
        int rest = exist[p.first]?cap:gas-p.second;
        if(gas >= p.second && d[p.first][rest] > d[place][gas] + p.second) {
          d[p.first][rest] = d[place][gas] + p.second;
          que.push({d[p.first][rest], p.first, rest});
        }
      }
    }

    int ans = LLINF;
    REP(i, cap+1) chmin(ans, d[goal][i]);
    if(ans==LLINF) cout << -1 << endl;
    else cout << ans << endl;
  }

  return 0;
}