AOJ 1318 Long Distance Taxi

問題

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

解法

単純に d[街の番号][残りのガソリン] で通ってしまって悲しいので，少し違う方針で．
まず，ガソリンスタンドについたら満タンにしてしまっていいので，ガソリンスタンドから cap を超えないように行ける街をあらかじめ M 回ダイクストラすることによって，新しいグラフを作る．新しい辺の重みはそのガソリンスタンドからの距離とする．（当たり前だが，辺を張るときは ガソリンスタンド -> 行ける街 のように張る．勢いで無向グラフにしないように．）
こうしてできたグラフの上で普通のダイクストラをすれば，上のような二次元配列を持つ必要はなくなる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

struct edge {
    int to, cost;
};

using edges = vector<edge>;
using graph = vector<edges>;

constexpr int INF = 1e9;

vector<int> dijkstra(graph& g, int s) {
    vector<int> d(g.size(), INF);
    priority_queue<pii, vector<pii>, greater<pii>> que;
    que.push(make_pair(0, s));
    d[s] = 0;
    while(!que.empty()) {
        pii p = que.top();
        que.pop();
        int v = p.second;
        if(d[v] < p.first) {
            continue;
        }
        for(auto& e : g[v]) {
            if(d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(make_pair(d[e.to], e.to));
            }
        }
    }
    return d;
}

int main() {
    int N, M, cap;
    while(cin >> N >> M >> cap, N) {
        unordered_map<string, int> idx;
        string src, dest;
        cin >> src >> dest;
        graph g(6001);
        idx[src] = 0; idx[dest] = 1;
        cap *= 10;
        for(int i=0; i<N; ++i) {
            string c1, c2;
            int d;
            cin >> c1 >> c2 >> d;
            if(idx.count(c1) == 0) {
                idx[c1] = idx.size();
            }
            if(idx.count(c2) == 0) {
                idx[c2] = idx.size();
            }
            g[idx[c1]].push_back(edge{idx[c2], d});
            g[idx[c2]].push_back(edge{idx[c1], d});
        }
        vector<int> S = {0, 1};
        for(int i=0; i<M; ++i) {
            string s;
            cin >> s;
            S.push_back(idx[s]);
        }
        graph g2(S.size());
        for(int i=0; i<S.size(); ++i) {
            auto d = dijkstra(g, S[i]);
            for(int j=0; j<S.size(); ++j) {
                if(d[S[j]] <= cap) {
                    g2[i].push_back(edge{j, d[S[j]]});
                }
            }
        }
        auto res = dijkstra(g2, 0);
        cout << (res[1] == INF ? -1 : res[1]) << endl;
    }
}