提出 #74602905

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 使用 1e18 作为无限大，确保不会越界且足够大
const long long INF = 1e18;

// 定义边的结构体
struct Edge {
    int to;
    long long weight;
};

int main() {
    // 优化标准输入输出的读取速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    // 邻接表表示图 (1-based index)
    vector<vector<Edge>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        // 有向边，从 u 指向 v
        adj[u].push_back({v, c});
    }

    // dist 数组记录从起点到其余各点的最短时间
    vector<long long> dist(n + 1, INF);
    dist[1] = 0;

    // 优先队列（最小堆），存储 pair<当前最短时间, 节点编号>
    // 默认的 priority_queue 是最大堆，所以要加上 greater 变成最小堆
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, 1});

    // Dijkstra 算法主循环
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        // 懒惰删除（Lazy Deletion）：如果拿出的距离大于记录的真实最短距离，说明它是过时的数据
        if (d > dist[u]) continue;

        // 由于所有边权均为正数，第一次从优先队列中取出目标终点时，就已确定是全局最短距离
        if (u == n) break;

        // 遍历所有相邻的节点
        for (const auto& edge : adj[u]) {
            int v = edge.to;
            long long w = edge.weight;

            // 松弛操作 (Relaxation)
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    // 输出到达终点 N 的最短时间
    cout << dist[n] << "\n";

    return 0;
}

提出情報

ジャッジ結果