AOJ 1162:Discrete Speed

問題リンク：Discrete Speed | Aizu Online Judge

問題概要：
スタート地点からゴール地点までの最短経路を求めろ
各エッジにはスピードの制限があり、そのエッジを移動する際はその制限速度以下でないといけない
最初にスタート地点を出るときはスピードが１でないといけない
同様にゴールに到着するときもスピードが１でないといけない
コストはノード間の距離÷スピードで計算する

使用した言語：C++

解法：
dequeを使って最短経路を求めた
各ノード間の関係は（ノード数）*(ノード数)だとメモリが怖いので2次元vectorを利用した
ノード間の最小コストは最大30*30*30なので3次元配列を作りそこに保存した
後は仕様にそって実装するだけだが意外と条件を忘れたりしてなぜか答えが１少ないという現象に見舞われた

メモ：
・最初にスタート地点からでるときはスピードが１でないといけない
　自分は int sp[] = {-1,0,+1}という配列をつくりループで速度を調整していたが、最初は１でなければならない事を忘れてがっつり3パターン試してしまった
もしSample Inputの3,4番の答えが１少ない現象に見舞われたらこれが原因

・ゴールにはスピード１でないと入れないというわけではない
　あくまで到着する時には１でないといけないというだけで通過するときは別に1でなくても良い

・queueを使いなんの工夫もなしにやると通らない
　最初はqueueで実装したが3秒以上かかりTLEとなってしまった
　そこでdequeに変更し、deque.frontのコストと今のコストを比べて今のコストの方が小さいならdequeのfrontにpushした。
　それ以外はdequeのbackにpushした
　もちろんdequeでpopする場所はfrontですよ

コード：

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<set>
#include<cmath>
#include<cstdio>
#include<queue>
#include<iomanip>
#include<deque>
#define F first
#define S second
#define MAX_N 32
#define MAX_D 32
#define INF (1<<28)
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;
typedef pair<double,double> P;
typedef pair<int,P> iP;
typedef pair<int,int> iiP;
typedef pair<iiP,P> PP;
typedef vector<vector<iP> > VViP;
int n,m,s,g;
VViP G;
double mincost[MAX_N][MAX_N][MAX_D]; // mincost[from][to][speed]
int sp[] = {-1,0,+1};

void dijkstra()
{

  deque<PP> deq; // iiPP(iiP(now,pre),P(cost,speed))

  
  deq.push_front(PP(iiP(s,s),P(0,1)));

  mincost[s][s][1] = 0; 
  double ans = INF;  

  
  while(!deq.empty())
    {
      PP p = deq.front(); deq.pop_front();
      int now,pre;
      double cost,speed;
      now = p.F.F, pre = p.F.S;
      cost = p.S.F, speed = p.S.S;

      if(cost >= ans)
	continue;      

      if(now == g && speed == 1)
	{
	  ans = min(ans,cost);	
	  continue;
	}	

      for(int i=0;i<G[now].size();i++)
	{
	  iP ip = G[now][i]; // VViP -> iP(to,P(distance,limit))
	  int to = ip.F;
	  double dis,lim;
	  dis = ip.S.F, lim = ip.S.S;
	  if(pre == to)
	    continue;

	  for(int j=0;j<3;j++)
	    {
	      double new_speed = speed + sp[j];
	      if(new_speed <= 0 || new_speed > lim)
		continue;

	      if(now == s && pre == s && new_speed != 1)
		continue;

	      if(mincost[now][to][(int)new_speed] > cost + (double)dis/new_speed)
		{
		  mincost[now][to][(int)new_speed] = cost + (double)dis/new_speed;

		  /*ここ重要*/
		  if(mincost[now][to][(int)new_speed] < deq.front().S.F)deq.push_front(PP(iiP(to,now),P(mincost[now][to][(int)new_speed],new_speed)));
		  else 
		    deq.push_back(PP(iiP(to,now),P(mincost[now][to][(int)new_speed],new_speed)));
		}
	    }

	}

    }
  

  if(ans == INF)
    cout << "unreachable" << endl;
  else 
    cout << setiosflags(ios::fixed) << setprecision(5) << ans << endl;
  
}

int main()
{

  while(true)
    {
      cin >> n >> m;
      if(n+m == 0)
	break;
      G.clear();
      G.resize(n+1);
      rep(i,n+1)
	rep(j,n+1)
	  rep(k,31)
	    mincost[i][j][k] = INF;

      cin >> s >> g;
      rep(i,m)
	{
	  int x,y;
	  double d,c;
	  cin >> x >> y >> d >> c;
	  G[x].push_back(iP(y,P(d,c)));
	  G[y].push_back(iP(x,P(d,c)));
	}
      
      dijkstra();
  
    }
  return 0;
}