結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー |
![]() |
提出日時 | 2022-01-11 17:34:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,706 bytes |
コンパイル時間 | 1,111 ms |
コンパイル使用メモリ | 84,016 KB |
実行使用メモリ | 17,628 KB |
最終ジャッジ日時 | 2024-11-14 11:41:12 |
合計ジャッジ時間 | 9,991 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 WA * 5 |
ソースコード
#include <iostream>#include <vector>#include <queue>using namespace std;using ll = long long;struct P{int to;ll cost;int i;P(ll cost, int to, int i): to(to), i(i), cost(cost){}bool operator>(const P &other) const {return this->cost > other.cost;}};bool chmin(ll &a, ll x){if(a > x){a = x;return true;}else return false;}int main(){int n, m;cin >> n >> m;vector<int> u(m), v(m), c(m), d(m);for(int i = 0; i < m; i++){cin >> u[i] >> v[i] >> c[i] >> d[i];u[i]--; v[i]--;}ll ans = 0;vector<bool> isused(m, false);for(int turn = 0; turn < 2; turn++){vector<vector<P>> G(n);for(int i = 0; i < m; i++){if(isused[i]) c[i] = d[i];G[u[i]].emplace_back(c[i], v[i], i);G[v[i]].emplace_back(c[i], u[i], i);}vector<ll> cost(n, 1LL << 60);vector<P> prev(n, P{-1, -1, -1});cost[0] = 0;priority_queue<P, vector<P>, greater<P>> Q;Q.emplace(0, 0, 0);while(!Q.empty()){auto c = Q.top(); Q.pop();if(cost[c.to] < c.cost) continue;for(auto &nex: G[c.to]){if(chmin(cost[nex.to], cost[c.to]+nex.cost)){prev[nex.to].to = c.to;prev[nex.to].i = nex.i;Q.emplace(cost[nex.to], nex.to, nex.i);}}}ans += cost[n-1];int cur = n-1;while(prev[cur].i != -1){isused[prev[cur].i] = true;cur = prev[cur].to;}}cout << ans << endl;return 0;}