Educational Codeforces Round 102 E問題
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, M, A[2d5], B[]; ll C[];
wgraph<ll> g;
ll res[];
{
int f1, f2, i, j, k, mask;
rd(N,M,(A--,B--,C)(M));
g.setEdge(N,M,A,B,C);
dimcomp3 dm(2,2,N);
DijkstraHeap<ll> hp;
hp.walloc(4*N);
hp.init(4*N);
rep(i,N) res[i] = ll_inf;
hp.change(0,0);
while(hp.size){
mask = hp.pop();
dm(mask, f1, f2, i);
if(f1==f2 && i > 0) res[i-1] <?= hp.val[mask];
rep(j,g.es[i]){
k = g.edge[i][j];
hp.change(dm(f1,f2,k), hp.val[mask]+g.cost[i][j]);
if(f1==0) hp.change(dm(1,f2,k), hp.val[mask]);
if(f2==0) hp.change(dm(f1,1,k), hp.val[mask]+2*g.cost[i][j]);
}
}
wt(res(N-1));
}
Current time: 2024年03月29日22時31分12秒
Last modified: 2021年02月27日13時04分31秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces
トップページに戻る
Logged in as: unknown user (not login)