ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1162 Discrete Speed

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1162


・概要
グラフが与えられて、出発地から目的地まで到達するまでの最短時間を求める問題です。
詳細は以下の通りです。
・出発地点では速度が1であり、目的地に到達するときも速度1でないといけない
・各ノードで自身の速度を下げる・維持する・上げることができる
(vを速さとすると、 v-1, v, v+1 のようになる)
・それぞれの辺には距離と制限速度が与えられる
・制限速度cは 1 <= c <= 30である
・移動時間は、距離/速さ で求めることができる
・同じノードを何度も移動してもよい


・解法
ダイクストラ法で解くことができます。

キューには[移動時間の合計、今いるノード、ひとつ前にいたノード、現在の速さ]を持たせます。
各ノードで速度を下げた・維持した・上げた状態をキューにいれていきます。

個人的な感想ですが、
この問題少し時間が厳しいような気がするので、ダイクストラをするときはきちんと枝を刈らないとTLEになると思います。


ソースコード

#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;

#define rep(i,n) for(int i = 0 ; i < (int)(n) ; i++)
static const double INF = (1 << 29);
static const double EPS = 1e-5;

struct State{
   double cost;
   int now, bef, speed;
   
   State(double c, int n, int b, int s):cost(c),now(n),bef(b),speed(s){}

   bool operator < (State s) const{
      return s.cost < cost;
   }
};
     
struct Edge{
   int to, dist, limit;
   Edge(int t, int d, int l):to(t),dist(d),limit(l){}
};

int n,m,s,g;
vector<Edge> edge[31];
double minCost[31][31][31];

double dijkstra(){
   rep(i,31)rep(j,31)rep(k,31)minCost[i][j][k] = INF;
   
   priority_queue<State>pq;
   pq.push(State(0,s,0,1));

   bool begin = true; 
   while(!pq.empty()){
      State p = pq.top();
      pq.pop();
      
      if(p.now==g && p.speed==1)return p.cost;
      
      if(minCost[p.now][p.bef][p.speed] <= p.cost + EPS)continue;
      minCost[p.now][p.bef][p.speed] = p.cost;
      
      for(int j = 0 ; j < edge[p.now].size() ; j++){
	 Edge e = edge[p.now][j];
	 if(p.bef==e.to)continue;

	 for(int k = -1 ; k <= 1 ; k++){
	    if(k!=0 && begin)continue;
	    
	    if(0 < p.speed + k && p.speed + k < 31 && p.speed + k <= e.limit){
	       double t = e.dist / (double)(p.speed + k);
	       if(minCost[e.to][p.now][p.speed+k] > p.cost+t){
		  pq.push(State(p.cost+t, e.to, p.now, p.speed+k));
	       }
	    }
	 }
      }
      if(begin)begin = false;
   }
   return -1.0;
}

int main(){
   while(scanf("%d%d",&n,&m)){
      if(n==0 && m==0)break;

      rep(i,31)edge[i].clear();

      cin >> s >> g;
      
      rep(i,m){
	 int x,y,d,c;
	 scanf("%d%d%d%d",&x,&y,&d,&c);
	 edge[x].push_back(Edge(y,d,c));
	 edge[y].push_back(Edge(x,d,c));
      }
      
      double ans = dijkstra();
      if(ans==-1)cout << "unreachable" << endl;
      else printf("%.10f\n",ans);
   }
   return 0;
}