Codeforces 187B AlgoRace

問題

n個の町がn^2本の道でつながっている。
車がm個あり、それぞれの車で町iからjまで行くのにかかるコストが与えられる。

ここでr回のレースをする。
i回目のレースではsiからtiまで移動する。
この際、車をki回まで乗り換えてよい。
車は任意の町で、時間0で乗り換えられる。同じ車を何度使ってもよい。

それぞれのレースでの、ゴールまでの最短時間を求めよ。

制約条件

n≦60
m≦60
r≦10^5
k≦1000

方針

頂点がn個しかないので、車は最大でもn-1回しか乗り換える必要がない。
なので、dp[k][i][j]を頂点iから出発して頂点jに
k回乗り換えて移動するときの最短距離として、これを更新するDPをすればよい。

まずそれぞれの車での距離行列をワーシャルフロイドしておく。
dp[0][i][j]は、好きな車を使ってiからjへ行く最短距離。
dp[k+1][i][j] = {dp[k][i][l] + dp[0][l][j]}である。

これで計算量がO(n^3(k+m))になって間に合う。

ソースコード

int n, m, r, d[60][60][60], dp[60][60][60];
int ans[100000];
pair<pi, pi> q[100000];

int main(){
	scanf("%d%d%d", &n, &m, &r);
	rep(i, m){
		rep(j, n) rep(k, n) scanf("%d", d[i][j] + k);
		rep(k, n) rep(ii, n) rep(j, n) d[i][ii][j] = min(d[i][ii][j], d[i][ii][k] + d[i][k][j]);
	}
	rep(i, n) rep(j, n){
		rep(k, 60) dp[k][i][j] = inf;
		rep(k, m) dp[0][i][j] = min(dp[0][i][j], d[k][i][j]);
	}
	rep(i, 59) rep(j, n) rep(k, n) rep(l, n){
		dp[i+1][j][l] = min(dp[i+1][j][l], dp[i][j][k] + dp[0][k][l]);
	}
	
	rep(i, r){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		printf("%d\n", dp[min(59, c)][a-1][b-1]);
	}
	
	return 0;
}