PKU 3635 Full Tank?
http://poj.org/problem?id=3635
ある街からある街まで燃料を補充しながら、最小のコストで移動したい。
距離を持つ無向グラフと、各ノードでの1ユニットの燃料補充にかかる値段が予め与えられる。
このとき、保持できる最大の燃料と、スタート地点、ゴール地点のクエリに対して最小のコストを答えろというような問題。
現在地と持ってる燃料でダイクストラしました。
計算量的にちょっと大きいかとも思いましたが、そこまで時間が厳しいわけではないようです。
bool vis[1000][103]; int pr[1000]; vector<PI> G[1000]; void solve(){ int c,s,e; cin>>c>>s>>e; memset(vis,0,sizeof(vis)); priority_queue<pair<int,PI> >q; q.push(mp(0,mp(s,0))); while(!q.empty()){ int cc=-q.top().F; int tv=q.top().S.F; int cap=q.top().S.S; q.pop(); if(tv==e){ printf("%d\n",cc); return; } if(vis[tv][cap])continue; vis[tv][cap]=true; if(cap<c && !vis[tv][cap+1]) q.push(mp(-cc-pr[tv],mp(tv,cap+1))); FOR(it,G[tv]){ int to=it->F; int d=it->S; if(d>cap || vis[to][cap-d])continue; q.push(mp(-cc,mp(to,cap-d))); } } cout<<"impossible"<<endl; } main(){ int n,m; cin>>n>>m; rep(i,n) cin>>pr[i]; rep(i,m){ int u,v,d; cin>>u>>v>>d; G[u].pb(mp(v,d)); G[v].pb(mp(u,d)); } int q; cin>>q; while(q--) solve(); }