Codeforces #412 Div1 D. Perishable Roads

これは思い浮かばなかった。
http://codeforces.com/contest/806/problem/D

問題

N頂点の完全グラフが与えられる。
各辺eには腐敗度P[e]が設定されている。

目的地となる頂点vを定めたとき、各頂点はそれぞれ次に移動すべき頂点を定めたとする。
その際、この定めた頂点に従うと、全頂点からいずれvに到達できるようにする。
各頂点iからvに移動するコストcost(i,v)は経由した辺のうち最小腐敗度とする。

各vに対し、それぞれ最適に移動先頂点を定めた場合、の最小値を求めよ。
なお、移動先頂点はv毎に異なる値を取れる。

解法

パスのコストが最大値や総和でなく最小値で決まるというのが珍しい。
まず、全腐敗度の最小値minPを求め、全腐敗度をminP分引いておこう。
答える場合には、その分あとでminP*(N-1)を足せばよい。

こうすると、どこかに腐敗度0の辺ができる。
辺(a,b)が腐敗度0とする場合、a→vの経路があるとして、余った頂点wはすべてw→bと辺を張ると、余った分の頂点に対応するコストが0になりよさそうである。
ただし、a→vを直接移動するのが必ずしも良いとは限らず、a→vの腐敗度が大きい場合、a→c→v等別の頂点を挟んだ方がいい場合もある。
この部分をもう少し真面目に評価しよう。

腐敗度0の辺(a,b)に対し、v_0←v_1←v_2…←v_k←b←(余った点) (v_0=v、v_k=a)のように移動先を指定したと仮定する。
また、v_iとv_i+1をつなぐ辺の腐敗度をw_iとする。
a=v_kより後ろの頂点は、腐敗度0の辺のためにコストが0になるので無視してよい。

この時、求める総コストはとなる。
この条件下では、コストが最小値となる場合、最後のw_(k-2)とw_(k-1)を除くと、w_i＞w_(i+1)となる。
仮にw_i＜w_(i+1)の場合、v_(i+1)→v_0のコストはw_iとなる。逆に言えば、w_(i+1)はw_i以上である時点でどんな値をとっても変わらない。
だとすると、無駄にパスを長くする必要はなく、さっさとaにつないでしまえばよい。
その結果、v_(i+2)=v_k=aとなるので、結局ラスト２本の辺以外はw_i＞w_(i+1)となる。

wが完全に降順に場合、上記のsumは結局minを無視してwのsumに等しくなる。
こうなると、結局これはパス上のコストの和を求めているのに等しいため、単にダイクストラで頂点間のコストを求めればよくなる。

ただ、この問題は実質全頂点間のコストを求める必要があるため、N回ダイクストラを実行することはできない。
そこでこれらをまとめて行おう。

(最小腐敗度減算後)腐敗度0の辺につながる頂点の距離を0とし、そこからダイクストラで各頂点への最小コストD(i)を求めよう。
求めたいのは各頂点からaへの距離だったが、逆にaに相当する点からダイクストラを行うことになる。

さて、D(i)を求めたら、本来求めたかったを計算することになる。
最初の減算分を考慮すると、 (minE(i)はiが接続された辺のうちminP減算後の最小コストの辺のコスト)となる。
先ほど、wは基本的に降順で最後の1個だけ昇順になりうると書いた。
だとすると、最初の1手は適当に最小腐敗度の辺を辿って移動すれば、次は直接aに移動してもその最小腐敗度分以上の追加コストが生じないため得である。
それより低いコストで移動するには、腐敗度降順のパスを求めるしかなく、それはダイクストラで計算済みであるため、この２値の小さい方を取ればよい。

int N;
ll P[2020][2020];
ll dist[2020];
int vis[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll mi=1LL<<60;
	for(i=0;i<N;i++) {
		for(j=i+1;j<N;j++) {
			cin>>P[i][j];
			P[j][i]=P[i][j];
			mi=min(mi,P[i][j]);
		}
	}
	
	FOR(x,N) {
		dist[x]=1LL<<60;
		FOR(y,N) if(x!=y) {
			P[x][y]-=mi;
			dist[x]=min(dist[x],P[x][y]*2);
		}
	}
	FOR(i,N) {
		int id=-1;
		FOR(x,N) if(vis[x]==0 && (id==-1 || dist[x]<dist[id])) id=x;
		vis[id]=1;
		FOR(y,N) dist[y]=min(dist[y],dist[id]+P[id][y]);
	}
	FOR(i,N) cout<<dist[i]+(N-1)*mi<<endl;
	
	
}

まとめ

本番ここまで考察が至らなかった。