题目分析与思路提示

1. 算法选择

这是一个标准的单源最短路径 (Single Source Shortest Path, SSSP) 问题。

• 图中有权值，且权值非负（消耗水不可能是负数）。
• 数据范围 $N, M \le 10^5$。
• Floyd算法：$O(N^3)$，太慢，不可用。
• Bellman-Ford / SPFA：最坏 $O(NM)$，容易被卡，不推荐。
• Dijkstra (堆优化版)：$O(M \log N)$。非常适合本题。

2. Dijkstra 算法流程

1. 初始化：
   • dis 数组：dis[1] = 0，其余设为无穷大 INF（表示尚未到达）。
   • vis 数组：false，表示节点是否已经确定了最短路。
   • 优先队列 pq：存储 pair<距离, 节点编号>，按距离从小到大排序。初始放入 {0, 1}。
2. 循环处理：
   • 当 pq 不为空时，取出堆顶元素（距离最小的点 $u$）。
   • 如果 $u$ 已经被处理过（vis[u] == true），跳过。
   • 标记 vis[u] = true。
   • 松弛操作 (Relax)：遍历 $u$ 的所有出边 $(u, v)$，权重为 $w$。
     • 如果 dis[u] + w < dis[v]：
       • 更新 dis[v] = dis[u] + w。
       • 将新状态 {dis[v], v} 推入优先队列。
3. 输出：
   • 如果 dis[N] == INF，说明不可达，输出 -1。
   • 否则输出 dis[N]。

3. 复杂度分析

• 每个节点最多被取出一次，每条边最多被扫描一次。
• 优先队列的操作是对数级的。
• 总时间复杂度 $O(M \log N)$。对于 $2 \times 10^5$ 的边数，计算量约为 $3 \times 10^6$，远小于 1 秒限时。

参考代码 (C++14)

/**
 * 题目：西行之路 (Journey to the West)
 * 难度：GESP 6级
 * 算法：Dijkstra (堆优化版)
 */

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

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

// 定义无穷大 (略大于可能的路径总和)
// 10^5 个点 * 1000 权值 = 10^8，int 足够
const int INF = 0x3f3f3f3f; 
const int MAXN = 100005;

// 结构体存储边
struct Edge {
    int to;
    int weight;
};

// 邻接表
vector<Edge> adj[MAXN];
// 距离数组
int dis[MAXN];
// 标记数组
bool vis[MAXN];

int main() {
    fast_io();

    int N, M;
    if (!(cin >> N >> M)) return 0;

    for (int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    // Dijkstra 初始化
    for (int i = 1; i <= N; ++i) {
        dis[i] = INF;
        vis[i] = false;
    }

    // 优先队列：pair<距离, 节点编号>
    // 默认是大根堆，我们需要小根堆，所以用 greater
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    // 起点
    dis[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        // 取出当前距离最小的点
        int u = pq.top().second;
        pq.pop();

        // 如果该点已经确定了最短路，跳过
        if (vis[u]) continue;
        vis[u] = true;

        // 遍历所有出边
        for (auto& edge : adj[u]) {
            int v = edge.to;
            int w = edge.weight;

            // 松弛操作
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                // 将更新后的节点放入堆中
                pq.push({dis[v], v});
            }
        }
    }

    if (dis[N] == INF) {
        cout << -1 << endl;
    } else {
        cout << dis[N] << endl;
    }

    return 0;
}

数据生成器 (Data Generator)

这是用于生成 1.in ~ 10.in 及其对应标准答案的生成器代码。覆盖了连通、不连通、链状、稠密图等情况。

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

const int INF = 0x3f3f3f3f;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
int solve(int N, const vector<tuple<int, int, int>>& edges) {
    vector<vector<pair<int, int>>> adj(N + 1);
    for (const auto& e : edges) {
        adj[get<0>(e)].push_back({get<1>(e), get<2>(e)});
    }

    vector<int> d(N + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    d[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        int dist = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (dist > d[u]) continue;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (d[u] + w < d[v]) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }

    return (d[N] == INF) ? -1 : d[N];
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, M;
        vector<tuple<int, int, int>> edges;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 5; M = 6;
            edges = {{1,2,2}, {1,3,10}, {2,3,3}, {2,4,8}, {3,5,1}, {4,5,5}};
        }
        else if (i == 2) {
            // 样例2 (不连通)
            N = 3; M = 2;
            edges = {{1,2,5}, {2,1,5}};
        }
        else if (i == 3) {
            // 链状 (1->2->3...->N)
            N = 100; M = N - 1;
            for(int k=1; k<N; k++) edges.emplace_back(k, k+1, randRange(1, 10));
        }
        else if (i == 4) {
            // 链状断开 (无解测试)
            N = 100; M = N - 2;
            for(int k=1; k<N-1; k++) edges.emplace_back(k, k+1, randRange(1, 10));
            // 缺少 N-1 -> N
        }
        else if (i == 5) {
            // 菊花图/辐射状 (1能到所有，但需要选最小)
            // 这里为了测试最短路，做多层结构
            N = 100; M = 200;
            for(int k=0; k<M; k++) {
                int u = randRange(1, N-1);
                int v = randRange(u+1, N); // 保证大致向后
                edges.emplace_back(u, v, randRange(1, 100));
            }
        }
        else {
            // 大规模随机图
            N = 100000;
            if (i == 6) M = N; // 稀疏，可能不连通
            else if (i == 7) M = N * 2; // 稍密
            else M = 200000; // 满 M

            // 为了保证 Case 8, 9, 10 大概率连通，先生成一条主干
            if (i >= 8) {
                for(int k=1; k<N; k++) {
                    // 以一定概率连接相邻点，保证从1能走到N
                    edges.emplace_back(k, k+1, randRange(100, 200)); 
                }
                // 剩余的边随机加，作为“捷径”
                int remain = M - (N - 1);
                for(int k=0; k<remain; k++) {
                    int u = randRange(1, N-1);
                    int v = randRange(u+1, min(N, u + 5000)); // 限制跨度，模拟局部道路
                    edges.emplace_back(u, v, randRange(1, 250)); // 捷径权值可能更小或更大
                }
            } else {
                // Case 6, 7 纯随机
                for(int k=0; k<M; k++) {
                    int u = randRange(1, N);
                    int v = randRange(1, N);
                    if(u != v) edges.emplace_back(u, v, randRange(1, 100));
                }
            }
        }

        // 写入输入
        fin << N << " " << edges.size() << "\n"; // M可能调整过
        for (const auto& e : edges) {
            fin << get<0>(e) << " " << get<1>(e) << " " << get<2>(e) << "\n";
        }

        // 写入输出
        fout << solve(N, edges) << endl;

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}