Google Code Jam 2017 Round 1B : C. Pony Express

解く前にTLでヒントを見てしまったのであっさり。
https://code.google.com/codejam/contest/8294486/dashboard#s=p2

問題

N個の町があり、一部の町同士の間は道でつながっている。
それぞれの道の長さは与えられる。なお、往路と復路で距離が異なる場合もある。

各町にはポニーがいる。
町iの各ポニーはパラメータとして移動可能な距離E[i]と移動速度S[i]を持つ。

Q個のクエリが与えられる。
各クエリは2つの町からなる。
両者の町をポニーを乗り継いで移動する場合、最短時間を求めよ。
なお、ポニーは自身が乗っているものしか移動させることができない。

解法

Warshall-Floyedを2回行えば解ける。

まず、1回目は普通に距離に対してWFを行い、2つの町の間の最短距離を求めよう。
そこから、ある町iでそこのポニーに乗った場合の、他の町までの最短移動時間を求めることができる。(ただし距離S[i]を超える町には到達不可)
改めてこの最短移動時間に対してWFを行い、乗り継ぎを行った場合の2つの町の間の最短移動時間を列挙しよう。

int N,Q;
int E[101],S[101];
ll D[101][101];
double T[101][101];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N>>Q;
	FOR(i,N) cin>>E[i]>>S[i];
	FOR(y,N) {
		FOR(x,N) {
			cin>>D[y][x];
			if(y==x) D[y][x]=0;
			else if(D[y][x]==-1) D[y][x]=1LL<<50;
		}
	}
	int z;
	FOR(z,N) FOR(x,N) FOR(y,N) D[x][y]=min(D[x][y],D[x][z]+D[z][y]);
	FOR(y,N) {
		FOR(x,N) {
			if(D[y][x]>E[y]) T[y][x]=1e15;
			else T[y][x]=D[y][x]*1.0/S[y];
		}
	}
	
	FOR(z,N) FOR(x,N) FOR(y,N) T[x][y]=min(T[x][y],T[x][z]+T[z][y]);
	_P("Case #%d:",_loop);
	FOR(i,Q) {
		cin>>x>>y;
		_P(" %.12lf",T[x-1][y-1]);
	}
	_P("\n");
	
}

まとめ

TLでヒント見てなくても、Bの方が手こずりそう。