AOJ0212 Highway Express Bus
Dijkstra
//AOJ0212 Highway Express Bus #include<iostream> #include<queue> #include<algorithm> #include<vector> using namespace std; #define INF 100000000 #define MAX_C 10 #define MAX_N 100 typedef pair<int,int> P; typedef pair<int, P> PP; int c,n,m,s,d; int cost[MAX_N][MAX_C + 1]; bool used[MAX_N][MAX_C + 1]; int line[MAX_N][MAX_N]; typedef priority_queue<PP, vector<PP>, greater<PP> > que; que dp; int dijkstra(){ while(!dp.empty()){ PP p = dp.top(); dp.pop(); P &x = p.second; if(used[x.second][x.first]) continue; used[x.second][x.first] = true; if(x.second == d){ return p.first; } for(int i = 0;i < n;i++){ if(cost[i][x.first] > p.first + line[x.second][i]){ cost[i][x.first] = p.first + line[x.second][i]; dp.push(PP(p.first + line[x.second][i], P(x.first, i))); } if(x.first > 0 && cost[i][x.first] > p.first + line[x.second][i] / 2){ cost[i][x.first - 1] = p.first + line[x.second][i] / 2; dp.push(PP(p.first + line[x.second][i] / 2, P(x.first - 1, i))); } } } } int main(){ int a,b,e; while(cin >> c >> n >> m >> s >> d, c){ if(c == 0)break; s--;d--; for(int i = 0;i < MAX_N;i++){ for(int j = 0; j < MAX_N;j++){ line[i][j] = INF; } } for(int i = 0; i < m;i++){ cin >> a >> b >> e; a--;b--; line[a][b] = e; line[b][a] = e; } for(int i = 0; i < MAX_N;i++){ for(int j = 0; j < MAX_C + 1;j++){ cost[i][j] = INF; used[i][j] = false; } } dp = que(); dp.push(PP(0, P(c, s))); cout << dijkstra() << endl; } return 0; }