結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | tails |
提出日時 | 2020-11-27 22:21:37 |
言語 | cLay (20240104-1) |
結果 |
WA
|
実行時間 | - |
コード長 | 732 bytes |
コンパイル時間 | 2,932 ms |
コンパイル使用メモリ | 185,012 KB |
実行使用メモリ | 25,248 KB |
最終ジャッジ日時 | 2023-09-19 01:53:32 |
合計ジャッジ時間 | 17,111 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,552 KB |
testcase_01 | AC | 2 ms
5,404 KB |
testcase_02 | WA | - |
testcase_03 | AC | 254 ms
20,912 KB |
testcase_04 | AC | 409 ms
25,048 KB |
testcase_05 | AC | 285 ms
22,656 KB |
testcase_06 | AC | 359 ms
23,940 KB |
testcase_07 | AC | 326 ms
22,116 KB |
testcase_08 | AC | 259 ms
21,108 KB |
testcase_09 | AC | 332 ms
23,224 KB |
testcase_10 | WA | - |
testcase_11 | AC | 363 ms
24,312 KB |
testcase_12 | AC | 377 ms
24,336 KB |
testcase_13 | AC | 326 ms
22,676 KB |
testcase_14 | AC | 328 ms
23,244 KB |
testcase_15 | AC | 318 ms
21,368 KB |
testcase_16 | AC | 427 ms
25,100 KB |
testcase_17 | AC | 343 ms
23,156 KB |
testcase_18 | AC | 302 ms
21,600 KB |
testcase_19 | AC | 365 ms
24,096 KB |
testcase_20 | AC | 375 ms
23,704 KB |
testcase_21 | AC | 347 ms
22,556 KB |
testcase_22 | AC | 388 ms
24,148 KB |
testcase_23 | AC | 333 ms
22,732 KB |
testcase_24 | AC | 379 ms
24,132 KB |
testcase_25 | AC | 407 ms
25,248 KB |
testcase_26 | AC | 351 ms
22,184 KB |
testcase_27 | AC | 376 ms
24,284 KB |
testcase_28 | AC | 281 ms
22,292 KB |
testcase_29 | WA | - |
testcase_30 | AC | 395 ms
24,988 KB |
testcase_31 | AC | 418 ms
24,840 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 438 ms
22,972 KB |
ソースコード
int u[1d5],v[1d5]; ll c[1d5],d[1d5]; map<pair<int,int>,ll> costmap; { int @n,@m; rd((u,v,c,d)(m)); rep(i,m){ costmap[{u[i],v[i]}]=c[i]|d[i]<<32; costmap[{v[i],u[i]}]=c[i]|d[i]<<32; } graph g; g.setEdge(n+1,m,u,v); ll sum=0; DijkstraHeap<ll> h; h.walloc(n+1); rep(2){ h.init(n+1); h.change(1,0); while(h.size){ int i=h.pop(); rep[g.edge[i]](j,g.es[i]){ long co=costmap[{i,j}]; h.change(j,h.val[i]+(int)co); } } sum+=h.val[n]; int i=n; do{ rep(k,g.es[i]){ int j=g.edge[i][k]; long co=costmap[{i,j}]; if(h.val[i]==h.val[j]+(int)co){ co>>=32; costmap[{i,j}]=co|co<<32; costmap[{j,i}]=co|co<<32; i=j; break; } } }while(i!=1); } wt(sum); }