AOJ 0212 Highway Express Bus
これは良問だと思った。
これを機にダイクストラ法の理解が一層深まった気がする。
解説
まず、下のコードではdpテーブルはdとおいて、d[0][i]に普通のダイクストラ法をやっていく。その後にmin(~,~)で割引券を使った時と使ってない時を判定して、最短経路を求めていく。
#include <cstdio> #include <vector> #include <algorithm> #include <utility> #include <queue> using namespace std; typedef pair<int, int> P; const int INF = 1 << 30; struct edge {int to, cost; }; int V; int d[100][100]; vector<edge> G[100]; priority_queue<P, vector<P>, greater<P> > que; void dijkstra(int s,int a){ for(int i = 0; i < V; i++) d[a][i] = INF; que.push(P(0, s)); d[a][s] = 0; while(!que.empty()){ P p = que.top(); que.pop(); int v = p.second; if(d[a][v] < p.first) continue; for(int i = 0; i < G[v].size(); i++){ edge e = G[v][i]; int Min = (a == 0 ? d[a][v] + e.cost : min(d[a][v] + e.cost, d[a-1][v] + e.cost/2)); if(d[a][e.to] > Min){ d[a][e.to] = Min; que.push(P(d[a][e.to], e.to)); } } } } int main(){ int c,m,s,e,From,To,Cost; edge E; while(scanf("%d%d%d%d%d",&c,&V,&m,&s,&e)!=EOF,c|V|m|s--|e--){ for(int i = 0; i < m; i++){ scanf("%d%d%d",&From,&To,&Cost); From--,To--; E.to = From,E.cost = Cost; G[To].push_back(E); E.to = To; G[From].push_back(E); } for(int i = 0; i <= c; i++) dijkstra(s, i); printf("%d\n",d[c][e]); for(int i = 0; i < 100; i++) G[i].clear(); } }