Codeforces ECR #102 : E. Minimum Path

本番は意外にAC数が少ない。
https://codeforces.com/contest/1473/problem/E

問題

重さ付きの無向辺を持つ連結グラフが与えられる。
パスのコストを、(パス上の辺の重さの総和)-(パス上の辺の重さの最大値)+(パス上の辺の重さの最小値)とする。
1番の頂点から、各頂点に至るパスのコストの最小値を求めよ。

解法

コストの計算式をよく見ると、1回だけ辺のコストを引き算でき、代わりに1回だけ辺のコストを加算しなければいけないことがわかる。
引き算・加算のタイミングは、一番都合のよい好きなタイミングで良いとみなすことができる。

あとは単純なダイクストラ法で、引き算・加算を1回行ったかどうかを状態として持ちながら、最小コストを順次計算できる。

int N,M;
vector<pair<int,int>> E[202020];
ll D[202020][4];

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,4) 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/4;
		int mask=Q.top().second%4;
		Q.pop();
		if(D[cur][mask]!=co) continue;
		FORR(e,E[cur]) FOR(i,4) if((mask&i)==0) {
			int add=e.second;
			if(i&1) add-=e.second;
			if(i&2) add+=e.second;
			if(D[e.first][mask|i]>co+add) {
				D[e.first][mask|i]=co+add;
				Q.push({-D[e.first][mask|i],e.first*4+(mask|i)});
			}
		}
	}
	for(i=1;i<N;i++) cout<<D[i][3]<<" ";
	cout<<endl;
}

まとめ

これは結構簡単。