aoj 1318 Long Distance Taxi
問題概要
グラフがあたえられる. 各頂点のいくつかはガソリンステーションでガソリンを入れることができる. ガソリンがなくならずに, スタートからゴールに行くまでの最短距離を求める.
またLPGのタンクの最大容量もあたえられる. 車の燃費は10km/Lである.
解法
dist[i][j] := 頂点iまで残りLPGがjで来た時の最短距離
という状態を拡張ダイクストラで計算していく.
気をつけなければならないところは, 与えられたcapと燃費10km/Lのままだと, 道の距離が1kmの時, タンクから0.1を引かなければならなくなり, 少数がでてしまう.
だから, capを10倍することでこれを回避できる.
ミス
ガソスタがあるときは, そこでガソリンを満タンにしてしまえばいい.
満タン以外にもすこしいれるなどの処理をしてしまったらTLEした. (下のコード参照)
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define REP(i,n) for(int i=n-1;i>=(0);i--) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define eall(v) unique(all(v), v.end()) #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; const ll INFF = 1e18; map<string, int> city2num; set<int> LPG; vector<pair<int, int>> G[6010]; int dist[6010][2010]; // dist[i][j] := 頂点iまで残りLPGがjで来た時の最短距離 using tup = tuple<int, int, int>; void dijkstra(int start, int cap){ rep(i, 6010)rep(j, 2010) dist[i][j] = INF; cap *= 10; dist[start][cap] = 0; priority_queue<tup, vector<tup>, greater<tup> > que; // 距離 頂点 残りのLPG que.push(make_tuple(0, start, cap)); while(!que.empty()){ int cost, u, lpg; tie(cost, u, lpg) = que.top(); que.pop(); if(dist[u][lpg] < cost) continue; for (auto& tmp : G[u]){ int v = tmp.first, di = tmp.second; int nlpg = lpg - di; int ncost = cost + di; if(nlpg < 0) continue; if(LPG.count(v)) { /* for (int i = nlpg; i <= cap; ++i){ これだとTLE(9.0s) if(dist[v][i] > ncost) { dist[v][i] = ncost; que.push(make_tuple(ncost, v, i)); } } */ if(dist[v][cap] > ncost) { dist[v][cap] = ncost; que.push(make_tuple(ncost, v, cap)); } }else{ if(dist[v][nlpg] > ncost) { dist[v][nlpg] = ncost; que.push(make_tuple(ncost, v, nlpg)); } } } } } string c1[6010], c2[6010]; int d[6010]; string s[6010]; int main(void) { while(1){ city2num.clear(); LPG.clear(); rep(i, 6010) G[i].clear(); int N, M, cap; scanf("%d %d %d", &N, &M, &cap); if(N == 0 && M == 0 && cap == 0) break; string src, dest; cin >> src >> dest; rep(i, N) cin >> c1[i] >> c2[i] >> d[i]; rep(i, M) cin >> s[i]; set<string> city; rep(i, N) city.insert(c1[i]), city.insert(c2[i]); int cnt = 0; for(auto& u : city) { city2num[u] = cnt++; } rep(i, M) LPG.insert(city2num[s[i]]); rep(i, N) G[city2num[c1[i]]].pb(mp(city2num[c2[i]], d[i])), G[city2num[c2[i]]].pb(mp(city2num[c1[i]], d[i])); int ns = city2num[src], nd = city2num[dest]; dijkstra(ns, cap); ll ans = INF; rep(i, cap * 10 + 1) chmin(ans, dist[nd][i]); if(ans != INF)printf("%lld\n", ans); else printf("-1\n"); } return 0; }