Codeforces #722 Div1 : D. It's a bird! No, it's a plane! No, it's AaParsa!

D問題の割にいつもより難しくない。
https://codeforces.com/contest/1528/problem/D

問題

N頂点M有効辺のグラフがある。
各辺は移動にかかる時間が与えられる。
また、各点の出次数は正である。
なお、時間が1すぎるごとに、各辺の行先が1ずつローテートする。

全頂点対において、移動にかかる最短時間を求めよ。

解法

f(u,v) := 頂点uから頂点vに至る最短時間
とする。ダイクストラ法の要領で、このテーブルを全部埋めよう。

f(u,v)がわかっているとき、v→wの遷移パターンを全部総当たりしながらf(u,w)の最小値を更新していけばよい。
この時、vから出ている辺を総当たりしながら、各遷移先wにかかる最短時間を計算したうえで、実際に遷移しよう。

int N,M;
ll C[606][606];
ll dp[606][606];



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(x,N) FOR(y,N) C[x][y]=1LL<<60;
	FOR(i,M) {
		cin>>x>>y>>k;
		C[x][y]=k;
	}
	FOR(x,N) FOR(y,N) dp[x][y]=1LL<<60;
	priority_queue<pair<ll,int>> Q;
	FOR(x,N) dp[x][x]=0, Q.push({0,x*1000+x});
	while(Q.size()) {
		ll co=-Q.top().first;
		int start=Q.top().second/1000;
		int cur=Q.top().second%1000;
		Q.pop();
		if(dp[start][cur]!=co) continue;
		ll to[606]={};
		FOR(i,N) to[(i+co)%N]=C[cur][i];
		FOR(i,2*N) {
			to[(i+1)%N]=min(to[(i+1)%N],to[i%N]+1);
		}
		FOR(x,N) if(dp[start][x]>co+to[x]) {
			dp[start][x]=co+to[x];
			Q.push({-dp[start][x],start*1000+x});
		}
	}
	
	FOR(y,N) {
		FOR(x,N) cout<<dp[y][x]<<" ";
		cout<<endl;
	}
}

まとめ

Nのサイズが600は微妙に大きいな…400か500でもいい気がするが。