結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | kappybar |
提出日時 | 2020-11-27 22:53:28 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,944 bytes |
コンパイル時間 | 1,983 ms |
コンパイル使用メモリ | 190,788 KB |
実行使用メモリ | 31,804 KB |
最終ジャッジ日時 | 2023-10-09 21:45:59 |
合計ジャッジ時間 | 15,629 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
8,296 KB |
testcase_01 | AC | 3 ms
8,216 KB |
testcase_02 | WA | - |
testcase_03 | AC | 312 ms
27,516 KB |
testcase_04 | AC | 373 ms
29,972 KB |
testcase_05 | AC | 375 ms
31,804 KB |
testcase_06 | AC | 344 ms
28,084 KB |
testcase_07 | AC | 362 ms
29,444 KB |
testcase_08 | AC | 329 ms
27,816 KB |
testcase_09 | AC | 335 ms
27,120 KB |
testcase_10 | WA | - |
testcase_11 | AC | 361 ms
28,800 KB |
testcase_12 | AC | 360 ms
28,760 KB |
testcase_13 | AC | 391 ms
30,284 KB |
testcase_14 | AC | 347 ms
27,268 KB |
testcase_15 | AC | 334 ms
28,268 KB |
testcase_16 | AC | 386 ms
29,824 KB |
testcase_17 | AC | 391 ms
30,440 KB |
testcase_18 | AC | 355 ms
28,744 KB |
testcase_19 | AC | 353 ms
28,540 KB |
testcase_20 | AC | 340 ms
27,732 KB |
testcase_21 | AC | 372 ms
30,024 KB |
testcase_22 | AC | 350 ms
27,996 KB |
testcase_23 | AC | 385 ms
30,320 KB |
testcase_24 | AC | 349 ms
28,200 KB |
testcase_25 | AC | 387 ms
29,872 KB |
testcase_26 | AC | 357 ms
29,472 KB |
testcase_27 | AC | 363 ms
28,808 KB |
testcase_28 | AC | 365 ms
29,272 KB |
testcase_29 | WA | - |
testcase_30 | AC | 384 ms
29,764 KB |
testcase_31 | AC | 378 ms
29,716 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 406 ms
30,908 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define chmin(x,y) x = min((x),(y)); #define chmax(x,y) x = max((x),(y)); using namespace std; using ll = long long ; using P = pair<int,int> ; using pll = pair<long long,long long>; const int INF = 1e9; const long long LINF = 1e17; const int MOD = 1000000007; //const int MOD = 998244353; const double PI = 3.14159265358979323846; int n = 100005; int m; vector<map<ll,ll>> graph(n); using p = pair<pll,int>; vector<ll> before(n); vector<ll> Dijkstra(int start){ vector<bool> seen(n,false); vector<ll> shortest(n,LINF); priority_queue<p,vector<p>,greater<p>> pq; pq.push(p(pll{0,start},-1)); while(!pq.empty()){ ll dist = pq.top().first.first; int node = pq.top().first.second; int b = pq.top().second; pq.pop(); if(seen[node]) continue; shortest[node] = dist; before[node] = b; seen[node] = true; for(auto next:graph[node]){ int next_node = next.first; ll next_cost = next.second; if(seen[next_node]) continue; pq.push(p(pll{next_cost + dist,next_node},node)); } } return shortest; } int main(){ cin >> n >> m; map<P,ll> dist; rep(i,m){ int u,v,c,d; cin >> u >> v >> c >> d; --u;--v; graph[u][v] = c; graph[v][u] = c; if(u>v) swap(u,v); dist[P(u,v)] = d; } //rep(i,n){ //for(auto p:graph[i]) //} vector<ll> res = Dijkstra(0); //rep(i,n) cout << res[i] << " "; //cout << endl; int now = n-1; while(now > 0){ int a = now; int b = before[now]; graph[a][b] = dist[P(min(a,b),max(a,b))]; graph[b][a] = graph[a][b]; now = b; //cout << now << endl; } vector<ll> ret = Dijkstra(n-1); cout << res[n-1] + ret[0] << endl; return 0; }