kmjp's blog

競技プログラミング参加記です

Codeforces #703 Div2 : E. Paired Payment

Eまではやけに簡単だった回。
https://codeforces.com/contest/1486/problem/E

問題

重み付きの辺を持つN頂点のグラフを考える。
駒を点から辺に沿って動かす。この時、互いにつながる2辺分まとめて駒を動かすことが出来、その際のコストは、両辺の重みの和の二乗とする。
1番の頂点から各頂点に至る最小コストを求めよ。

解法

幸い重みのバリエーションは少ない。
そこで、奇数本目の辺の移動と偶数本目の辺の移動を分けて考え、奇数本目の移動後は、その時の辺の重みを覚えておくようにしよう。
あとは単純なダイクストラ法で解くことができる。

int N,M;
vector<pair<int,int>> E[101010];
ll D[101010][51];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>r;
		E[x-1].push_back({y-1,r});
		E[y-1].push_back({x-1,r});
	}
	FOR(i,N) FOR(j,51) D[i][j]=1LL<<60;
	D[0][0]=0;
	priority_queue<pair<ll,int>> Q;
	Q.push({0,0});
	while(Q.size()) {
		ll co=-Q.top().first;
		int cur=Q.top().second/100;
		int d=Q.top().second%100;
		
		Q.pop();
		if(D[cur][d]!=co) continue;
		if(d==0) {
			FORR2(e,c,E[cur]) if(D[e][c]>co) {
				D[e][c]=co;
				Q.push({-co,e*100+c});
			}
		}
		else {
			FORR2(e,c,E[cur]) if(D[e][0]>co+(d+c)*(d+c)) {
				D[e][0]=co+(d+c)*(d+c);
				Q.push({-D[e][0],e*100});
			}
		}
	}
	FOR(i,N) {
		if(D[i][0]==1LL<<60) cout<<-1<<" ";
		else cout<<D[i][0]<<" ";
	}
	cout<<endl;
	
	
}

まとめ

重みの上限が小さいことに気が付けば、そこからすぐだね。