Eまではやけに簡単だった回。
https://codeforces.com/contest/1486/problem/E
問題
重み付きの辺を持つN頂点のグラフを考える。
駒を点から辺に沿って動かす。この時、互いにつながる2辺分まとめて駒を動かすことが出来、その際のコストは、両辺の重みの和の二乗とする。
1番の頂点から各頂点に至る最小コストを求めよ。
解法
幸い重みのバリエーションは少ない。
そこで、奇数本目の辺の移動と偶数本目の辺の移動を分けて考え、奇数本目の移動後は、その時の辺の重みを覚えておくようにしよう。
あとは単純なダイクストラ法で解くことができる。
int N,M; vector<pair<int,int>> E[101010]; ll D[101010][51]; 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,51) 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/100; int d=Q.top().second%100; Q.pop(); if(D[cur][d]!=co) continue; if(d==0) { FORR2(e,c,E[cur]) if(D[e][c]>co) { D[e][c]=co; Q.push({-co,e*100+c}); } } else { FORR2(e,c,E[cur]) if(D[e][0]>co+(d+c)*(d+c)) { D[e][0]=co+(d+c)*(d+c); Q.push({-D[e][0],e*100}); } } } FOR(i,N) { if(D[i][0]==1LL<<60) cout<<-1<<" "; else cout<<D[i][0]<<" "; } cout<<endl; }
まとめ
重みの上限が小さいことに気が付けば、そこからすぐだね。