AOJ 1162 - Discrete Speed
問題概要
N個の都市とM本のエッジがあり、各エッジには距離dと制限速度cが与えられている。出発地sから速度1で出発し、目的地gへ速度1で到達するための最短時間を求めよ。ただし、ある都市に速度vで到達した場合、その都市から次の都市へは速度v-1, v, v+1のいずれかで移動することができるが、移動中のエッジの制限速度を超えてはならない。Uターンは禁止である。同じ都市やエッジに複数回訪れても良く、出発地や目的地も経由しても良い。目的地に到達できない場合は、"unreachable"を出力せよ。
制約
- 2 ≤ N ≤ 30
- 1 ≤ di ≤ 100
- 1 ≤ ci ≤ 30
解法
dijkstra。
Time[今の都市][今の速度][前の都市] := 最短時間。
感想
Uターンの処理をしていたつもりがしていなくてWAを連発してしまった…。
コード
#include <bits/stdc++.h> using namespace std; #define MAX 35 #define INF 1e9 #define F first #define S second typedef pair<double,int> pdi; typedef pair<int,int> pii; typedef pair<pdi,pii> State; struct Edge{ int to,d,c; Edge(int to,int d,int c) : to(to),d(d),c(c) {} }; int N,M,s,g; vector<Edge> G[MAX]; double dijkstra(){ priority_queue<State,vector<State>,greater<State> > Q; Q.push(State(pdi(0,s),pii(1,N))); double Time[MAX][MAX][MAX]; fill(Time[0][0],Time[0][0]+MAX*MAX*MAX,INF); Time[s][1][N] = 0; while(!Q.empty()){ State p = Q.top(); Q.pop(); int v = p.F.S, vel = p.S.F; if(Time[v][vel][p.S.S] < p.F.F) continue; if(v == g && vel == 1){ return Time[g][1][p.S.S]; } for(int i = 0 ; i < (int)G[v].size() ; i++){ for(int j = -1 ; j <= 1 ; j++){ if(vel+j <= 0) continue; if(Time[v][vel][p.S.S] == 0 && j){ continue; } Edge e = G[v][i]; if(e.to == p.S.S) continue; double t = (double)e.d/(vel+j); if(vel+j <= e.c && Time[v][vel][p.S.S] + t < Time[e.to][vel+j][v]){ Time[e.to][vel+j][v] = Time[v][vel][p.S.S] + t; Q.push(State(pdi(Time[e.to][vel+j][v],e.to),pii(vel+j,v))); } } } } return INF; } int main(){ int x,y,d,c; while(cin >> N >> M, N){ for(int i = 0 ; i < MAX ; i++){ G[i].clear(); } cin >> s >> g; s--; g--; for(int i = 0 ; i < M ; i++){ cin >> x >> y >> d >> c; x--; y--; G[x].push_back(Edge(y,d,c)); G[y].push_back(Edge(x,d,c)); } double res = dijkstra(); if(res == INF){ cout << "unreachable" << endl; }else{ printf("%.8f\n",res); } } return 0; }