AtCoder ARC #052 : C - 高橋くんと不思議な道

ABは良かったけどCDがグダりすぎた。
http://arc052.contest.atcoder.jp/tasks/arc052_c

問題

N頂点M辺の連結無向グラフがある。
各辺はタイプA,Bの２種類あり、それぞれ移動コストは以下のように計算される。

• タイプA : 常に1
• タイプB : 過去に通ったタイプBの辺の数+1

頂点0から各頂点に移動する最小コストを求めよ。

解法

dp[v][b] := 頂点0からvに移動する際、タイプBの辺をb回通った場合、タイプAの辺を通った数
とする。解はmin_b(dp[v][b] + b*(b+1)/2)となる。

あとはbの小さい順にダイクストラをやっていけば良い。
その際若干の枝刈りが必要で、i=0～(b-1)におけるdp[v][i]の最小値をCとすると、dp[v][b] ＜ C+bでない限りは、タイプBをb回通るメリットはないのでそれ以上探索しない。

int N,M;
vector<pair<int,int>> E[10100];
ll dist[10101];
ll mi[10101];
ll from[10101];
ll to[10101];
priority_queue<pair<ll,int>> Q[10100];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>r>>x>>y;
		E[x].push_back({y,r});
		E[y].push_back({x,r});
	}
	FOR(i,N) dist[i]=from[i]=mi[i]=1LL<<60;
	from[0]=0;
	Q[0].push({0,0});
	FOR(i,10005) {
		FOR(x,N) to[x]=1LL<<60;
		while(Q[i].size()) {
			auto r=Q[i].top();
			Q[i].pop();
			ll cost=-r.first;
			int cur=r.second;
			if(cost!=from[cur]) continue;
			
			mi[cur]=min(mi[cur],from[cur]);
			dist[cur]=min(dist[cur],from[cur]+1LL*i*(i+1)/2);
			
			FORR(e,E[cur]) {
				if(e.second==0) {
					if(from[e.first]>from[cur]+1 && from[cur]+1<mi[e.first]) {
						from[e.first]=from[cur]+1;
						Q[i].push({-from[e.first],e.first});
					}
				}
				else {
					if(to[e.first]>from[cur] && from[cur]+i<mi[e.first]) {
						to[e.first]=from[cur];
						Q[i+1].push({-to[e.first],e.first});
					}
				}
			}
		}
		swap(from,to);
	}
	
	FOR(i,N) cout<<dist[i]<<endl;
	
}

まとめ

枝刈りちゃんとしなかったおかげで最後のケースで2WAした。