提出 #74603768

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef long long ll;
typedef pair<ll, int> pli;

const int MAXN = 1e5 + 5;
vector<pli> g[MAXN];
ll dist[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    // 建图
    for (int i = 0; i < M; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        g[u].emplace_back(c, v);
    }

    // 初始化距离
    fill(dist, dist + N + 1, LLONG_MAX);
    dist[1] = 0;

    // 优先队列（小根堆）
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.emplace(0, 1);

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;
        if (u == N) break; // 提前退出

        for (auto [w, v] : g[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.emplace(dist[v], v);
            }
        }
    }

    cout << dist[N] << endl;
    return 0;
}

提出情報

ジャッジ結果