CODE THANKS FESTIVAL 2015 : G - カメレオン

やるだけ…？
http://code-thanks-festival-2015-open.contest.atcoder.jp/tasks/code_thanks_festival_2015_g

注：12/7 22:30頃 O(E^2)解からO((N+E)*logE)位の解に修正しました。

問題

N個の広場と、広場同士を結ぶM個の道が与えられる。
カメレオンが1番の広場からN番の広場に移動することを考える。

各道を通るには移動時間T[i]がかかる。
また通過時には自身の体の色をC[i]にしなければならない。
体の変色には、変色前後の色値の差分の絶対値の時間がかかる。

カメレオンは初期状態で広場１にいて体の色が１であるとき、N番の広場に到達する最短時間を求めよ。

解法

各広場ごとに、その広場に出入りする道に対応する色の数だけ(広場,色)の対に対応する頂点を作ろう。
例えばテストケース１では広場２は色[1,3,6]のいずれかで出入りしうるので、(2,1),(2,3),(2,6)と3つ頂点を作る。

そして次の2種類の辺を張る。

• 入力の道に対応する(広場,色)同士で辺を張る。移動コストはT[i]。
• 同じ広場内で大小順で隣接する色に対応する頂点間で辺を張る。移動コストは色の差の絶対値。

あとはダイクストラで広場Nに対応するいずれかの頂点に到達する最小コストを求めよう。

int N,M;
int A[180800],B[180800],C[180800],T[180800];
int F[101010];
vector<int> H[101010];

vector<pair<int,int> > E[303030];
ll CO[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	H[0].push_back(1);
	FOR(i,M) {
		cin>>A[i]>>B[i]>>C[i]>>T[i];
		A[i]--;
		B[i]--;
		H[A[i]].push_back(C[i]);
		H[B[i]].push_back(C[i]);
	}
	
	FOR(i,N) {
		if(i) F[i]=F[i-1]+H[i-1].size();
		sort(ALL(H[i]));
		H[i].erase(unique(ALL(H[i])),H[i].end());
		FOR(j,H[i].size()) {
			if(j) E[F[i]+j].push_back({F[i]+j-1,H[i][j]-H[i][j-1]});
			if(j<H[i].size()-1) E[F[i]+j].push_back({F[i]+j+1,H[i][j+1]-H[i][j]});
		}
	}
	FOR(i,M) {
		x = lower_bound(H[A[i]].begin(),H[A[i]].end(),C[i])-H[A[i]].begin();
		y = lower_bound(H[B[i]].begin(),H[B[i]].end(),C[i])-H[B[i]].begin();
		E[F[A[i]]+x].push_back({F[B[i]]+y,T[i]});
		E[F[B[i]]+y].push_back({F[A[i]]+x,T[i]});
	}
	
	FOR(i,300000) CO[i]=1LL<<60;
	CO[0]=0;
	priority_queue<pair<ll,int>> PQ;
	PQ.push({0,0});
	
	while(PQ.size()) {
		auto k=PQ.top();
		PQ.pop();
		ll cost=-k.first;
		int cur=k.second;
		if(CO[cur]!=cost) continue;
		if(cur>=F[N-1]) return _P("%lld\n",cost);
		FORR(r,E[cur]) {
			ll nc=cost+r.second;
			
			if(CO[r.first]>nc) {
				CO[r.first] = nc;
				PQ.push({-nc,r.first});
			}
		}
	}
	
}

まとめ

自分以外にもO(N^2)とかO(E^2)で通してる人いそう。