離散的速度

拡張ダイクストラとBFSの違いがまだよくわかってない。
去年のICPC国内予選のD問題です。
問題文が終了間際まで正しく理解できてなかったという悲しい問題でした。

離散的速度

Problem D : http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1162&lang=jp

状態としての情報が1個足りないことに気付けなくて、データセットがなかなか通らなかった。
最初は単純なキューを使って実装したけど、コアダンプしたので素直にループで回す方針に切り替えた。
データセットは通るけれど、AOJジャッジはTLE喰らう。優先度付きキューで実装したら通るかな。


拡張ダイクストラ。
[現在のノード][前回のノード][速度]　の3つ情報で1つの状態を作る。
最初は前回のノードを別に保存していて、所要時間を記録するときにどのノードから来ても
同じメモリに記憶してたのが間違いでした。

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

double memo[32][32][32];
char	visited[32][32][32];
int N,M,S,G;
struct e {
	int d,c;
}edge[32][32];

int main()
{
	for(;cin>>N>>M,N||M;){
		double inf = 9999999.0;
		for(int i=0;i<32;i++)for(int j=0;j<32;j++)
			edge[i][j].d = edge[i][j].c = -1;
		for(int i=0;i<32;i++)for(int j=0;j<32;j++)for(int k=0;k<32;k++)
			memo[i][j][k]=inf, visited[i][j][k]=0;
		
		cin>>S>>G;
		for(int i=0;i<M;i++){
			int x,y,d,c;
			cin>>x>>y>>d>>c;
			edge[x][y].d = edge[y][x].d = d;
			edge[x][y].c = edge[y][x].c = c;
		}

		memo[S][S][0] = 0.0;
		while(1){
			int nowCity, prevCity, nowVel;
			double  nowTime = inf;
			
			for(int i=1;i<=N;i++)
				for(int j=1;j<=N;j++)
					for(int k=0;k<=30;k++){
						if(visited[i][j][k] || nowTime < memo[i][j][k])continue;
						nowTime = memo[i][j][k];
						nowCity = i;
						prevCity = j;
						nowVel = k;
					}
			if(nowTime == inf){ puts("unreachable"); break; }
			if(nowCity == G && nowVel == 1){
				printf("%lf\n",nowTime);
				break;
			}
			
			visited[nowCity][prevCity][nowVel] = 1;
			
			for(int nextVel=nowVel-1;nextVel<=nowVel+1;nextVel++){
				if(nextVel<=0)continue;
				for(int nextCity=1;nextCity<=N;nextCity++){
					if(edge[nowCity][nextCity].d == -1 || nextCity==prevCity)continue;
					if(edge[nowCity][nextCity].c < nextVel)continue;
					memo[nextCity][nowCity][nextVel] = min( memo[nextCity][nowCity][nextVel],
													 (double)edge[nowCity][nextCity].d/nextVel+nowTime);

				}
			}
		}
	}
	return 0;
}