なんか速度が不安定。
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; } } } }
まとめ
ちょっと重すぎ…。