AIM Tech Round 4 : D. Dynamic Shortest Path

なんか速度が不安定。
http://codeforces.com/contest/843/problem/D

問題

重み付無向グラフが与えられる。
以下のクエリを順次処理せよ。

• 頂点1から指定された頂点vまでの最短距離を答える。
• 指定された辺の長さを1ずつ伸ばす。

解法

まず最初にダイクストラ法を実行しよう。

以後後者のクエリに対して毎回ダイクストラ法を実行する。
ただし、クエリの結果頂点1から各頂点までの距離は、最大で伸ばされた辺の数までしか増えない。
よって、priority_queue等の重いデータ構造で距離を直接管理するのではなく、増分距離に関してvectorやqueue等の軽いデータ構造を用いて管理する。

ただこの問題はかなり定数倍の最適が必要なため、最も深いループ内は極力軽くしないと時間内に通らない。

int N,M,Q;
int A[101010],B[101010],C[101010];
vector<pair<int,int>> E[101010];

ll ret[101010];
ll add[101010];
queue<int> ev[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&N,&M,&Q);
	FOR(i,M) {
		scanf("%d%d%d",&A[i],&B[i],&C[i]);
		A[i]--;
		B[i]--;
		E[A[i]].push_back({B[i],C[i]});
		C[i]=E[A[i]].size()-1;
	}
	
	FOR(i,N) ret[i]=1LL<<60, add[i]=1LL<<50;
	ret[0]=0;
	priority_queue<pair<ll,int>> PQ;
	PQ.push({0,0});
	while(PQ.size()) {
		ll co=-PQ.top().first;
		int cur=PQ.top().second;
		PQ.pop();
		if(ret[cur]!=co) continue;
		FORR(e,E[cur]) if(ret[e.first]>co+e.second) {
			ret[e.first]=co+e.second;
			PQ.push({-ret[e.first],e.first});
		}
	}
	
	
	while(Q--) {
		scanf("%d%d",&x,&y);
		if(x==1) {
			cout<<((ret[y-1]>=1LL<<60)?-1:ret[y-1])<<endl;
		}
		else {
			
			FOR(i,y) scanf("%d",&x), E[A[x-1]][C[x-1]].second++;
			add[0]=0;
			ev[0].push(0);
			FOR(i,y+1) {
				while(!ev[i].empty()) {
					int cur=ev[i].front();
					ev[i].pop();
					if(add[cur]!=i) continue;
					FORR(e,E[cur]) {
						ll d = ret[cur]+add[cur]-ret[e.first]+e.second;
						if(d<=y && add[e.first]>d) {
							add[e.first]=d;
							ev[add[e.first]].push(e.first);
						}
					}
				}
			}
			FOR(i,N) {
				ret[i]+=add[i];
				add[i]=1LL<<50;
			}
		}
		
	}
}

まとめ

ちょっと重すぎ…。