Codeforces 187 B. AlgoRace

問題

n個の都市があり、m種類の車を使ったときの、
それぞれの都市aから都市bへ移動するのにかかる時間が与えられる。

このとき、以下のクエリr個に答えよ。
都市s[i]から都市t[i]へ、車の交換回数t[i]回以下で移動するときにかかる最小の時間。
ただし、車は好きな都市で、時間0で、好きな車に乗り換えられるものとする。

制約条件

n≦60
m≦60
r≦10^5

方針

都市iから都市jへ、乗り換え回数k回で移動するのにかかる最小時間をdp[i][j][k]とする。
すると、dp[i][j][k]は、dp[i][j][k-1]に、どこかで一回乗り換えが加わったものであるから、
dp[i][j][k] = min{dp[i][x][k-1] + dp[x][j][0] | xはどこかの都市}と書ける。

この漸化式にしたがってDPを最初にしておけば、各クエリに対してO(1)時間で答えることができる。

ソースコード

int n, m, r;
int d[60][60][60], dp[60][60][61];

void run()
{
	cin >> n >> m >> r;
	rep(l, m){
		rep(i, n) rep(j, n) cin >> d[l][i][j];
		rep(k, n) rep(i, n) rep(j, n) d[l][i][j] = min(d[l][i][j], d[l][i][k] + d[l][k][j]);
	}
	
	rep(k, 61) rep(i, n) rep(j, n) dp[i][j][k] = inf;
	rep(i, n) rep(j, n){
		rep(k, m) dp[i][j][0] = min(dp[i][j][0], d[k][i][j]);
	}
	
	rep(i, 60) rep(a, n) rep(b, n){
		rep(c, n) dp[a][b][i + 1] = min(dp[a][b][i + 1], dp[a][c][i] + dp[c][b][0]);
	}
	rep(i, r){
		int a, b, t;
		cin >> a >> b >> t;
		t = min(t, 60);
		cout << dp[a-1][b-1][t] << endl;
	}
}