結果

問題 No.1301 Strange Graph Shortest Path
ユーザー otogawa
提出日時 2025-04-22 09:09:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,482 bytes
コンパイル時間 2,815 ms
コンパイル使用メモリ 207,284 KB
実行使用メモリ 17,500 KB
最終ジャッジ日時 2025-04-22 09:09:17
合計ジャッジ時間 11,381 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 28 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define int ll
#define fast_io cin.tie(0)->sync_with_stdio(0);
#define endl '\n'
typedef long long ll;

int32_t main() {
	fast_io;

    int n, m; cin >> n >> m;
    using T = array<int, 4>;
    using E = pair<int, int>;
    vector<T> edges;
    vector<vector<E>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w, t; cin >> u >> v >> w >> t;
        edges.push_back({u - 1, v - 1, w, t});
        g[u - 1].push_back({v - 1, i});
        g[v - 1].push_back({u - 1, i});
    }
    vector<int> state(m);

    vector<int> dist(n);
    vector<pair<int, int>> par(n);
    const int INF = 1e18;
    auto dijkstra = [&] (int s) {
        fill(dist.begin(), dist.end(), INF);
        dist[s] = 0;
        priority_queue<E, vector<E>, greater<E>> pq;
        pq.emplace(dist[s], s);
        while (pq.size()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u]) continue;
            for (auto [v, i] : g[u]) {
                int w = edges[i][2 + state[i]];
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    par[v] = {u, i};
                    pq.emplace(dist[v], v);
                }
            }
        }
    };
    dijkstra(0);
    int ans = dist[n - 1];
    int at = n - 1;
    while (at != 0) {
        state[par[at].second]++;
        at = par[at].first;
    }
    dijkstra(0);
    ans += dist[n - 1];

    cout << ans << endl;
}
0