题目分析与思路提示

1. 为什么不用 Dijkstra？

• Dijkstra 是单源最短路。如果我们要查询 $Q$ 次，且起点 $S$ 各不相同，我们需要对每个起点跑一遍 Dijkstra。
• 总复杂度：$Q \times M \log N$。
• 当 $N$ 很小 ($200$) 但 $Q$ 很大时，Floyd 算法代码极短，且常数极小，非常适合处理这种全源最短路问题。
• 最重要的是：Floyd 是基于邻接矩阵的，可以直接查询 dis[S][T] 得到答案，响应时间是 $O(1)$。

2. 算法流程 (Floyd-Warshall)

1. 初始化邻接矩阵：
   • dis[i][j] 初始化为无穷大 (INF)。
   • dis[i][i] 初始化为 0（自己到自己距离为0）。
2. 读入边：
   • 读入 $u, v, w$。
   • dis[u][v] = dis[v][u] = min(dis[u][v], w)。
   • 坑点：可能有重边（两条路连接同一对城市），要保留最短的那条。
3. 三层循环（核心）：
   • 外层循环枚举中转点 $k$（从 1 到 $N$）。
   • 中间层枚举起点 $i$。
   • 内层枚举终点 $j$。
   • 更新：dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])。
4. 处理查询：
   • 直接输出 dis[S][T]。如果值为 INF，输出 -1。

3. 复杂度分析

• 时间复杂度：$O(N^3)$。
  • $N=200$，运算量 $200^3 = 8,000,000$，非常快（1秒内）。
  • 这也是为什么 Floyd 题目通常 $N \le 300$ 的原因。
• 空间复杂度：$O(N^2)$，用于存储邻接矩阵。

参考代码 (C++14)

/**
 * 题目：周游列国 (Touring the States)
 * 难度：GESP 6级
 * 算法：Floyd-Warshall (全源最短路)
 * 复杂度：O(N^3)
 */

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

using namespace std;

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

// 定义无穷大，要注意防止加法溢出
// 200个点，边权最大1000，路径最长 200*1000 = 2*10^5。
// 0x3f3f3f3f (约10^9) 足够大且相加不溢出 int
const int INF = 0x3f3f3f3f;
const int MAXN = 205;

// 邻接矩阵存储距离
int dis[MAXN][MAXN];

int main() {
    fast_io();

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

    // 1. 初始化矩阵
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (i == j) dis[i][j] = 0;
            else dis[i][j] = INF;
        }
    }

    // 2. 读入边
    for (int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        // 坑点：处理重边，取最小值
        dis[u][v] = min(dis[u][v], w);
        dis[v][u] = min(dis[v][u], w);
    }

    // 3. Floyd 核心算法
    // k: 中转点 (必须放在最外层！)
    for (int k = 1; k <= N; ++k) {
        // i: 起点
        for (int i = 1; i <= N; ++i) {
            // j: 终点
            for (int j = 1; j <= N; ++j) {
                // 如果 i->k 和 k->j 都可达，尝试更新
                if (dis[i][k] != INF && dis[k][j] != INF) {
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }
    }

    // 4. 处理查询
    for (int i = 0; i < Q; ++i) {
        int s, t;
        cin >> s >> t;
        if (dis[s][t] == INF) {
            cout << -1 << endl;
        } else {
            cout << dis[s][t] << endl;
        }
    }

    return 0;
}

数据生成器 (Data Generator)

用于生成 1.in ~ 10.in 及其标准答案。

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

using namespace std;

const int INF = 0x3f3f3f3f;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
void solve(int N, int M, int Q, const vector<tuple<int, int, int>>& edges, const vector<pair<int, int>>& queries, ofstream& fout) {
    // 动态申请二维数组，防止栈溢出（虽然N=200不大）
    vector<vector<int>> d(N + 1, vector<int>(N + 1, INF));

    for (int i = 1; i <= N; ++i) d[i][i] = 0;

    for (const auto& e : edges) {
        int u = get<0>(e);
        int v = get<1>(e);
        int w = get<2>(e);
        d[u][v] = min(d[u][v], w);
        d[v][u] = min(d[v][u], w);
    }

    for (int k = 1; k <= N; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (d[i][k] != INF && d[k][j] != INF) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }

    for (const auto& q : queries) {
        int ans = d[q.first][q.second];
        fout << (ans == INF ? -1 : ans) << "\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, Q;
        vector<tuple<int, int, int>> edges;
        vector<pair<int, int>> queries;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 4; M = 4; Q = 3;
            edges = {{1,2,2}, {2,3,3}, {1,3,6}, {3,4,2}};
            queries = {{1,3}, {1,4}, {2,4}};
        }
        else if (i == 2) {
            // 样例2 (不连通)
            N = 3; M = 1; Q = 2;
            edges = {{1,2,10}};
            queries = {{1,3}, {2,3}};
        }
        else if (i <= 4) {
            // 小规模稠密
            N = 20; M = 100; Q = 50;
            for(int k=0; k<M; k++) edges.emplace_back(randRange(1, N), randRange(1, N), randRange(1, 20));
            for(int k=0; k<Q; k++) queries.emplace_back(randRange(1, N), randRange(1, N));
        }
        else if (i == 5) {
            // 链状 (测试中转能力)
            N = 50; M = N-1; Q = 50;
            for(int k=1; k<N; k++) edges.emplace_back(k, k+1, 10);
            for(int k=0; k<Q; k++) queries.emplace_back(1, N);
        }
        else if (i == 6) {
            // 重边测试
            N = 50; M = 200; Q = 50;
            for(int k=0; k<M; k++) edges.emplace_back(randRange(1, 10), randRange(1, 10), randRange(1, 100)); // 集中在前10个点
            for(int k=0; k<Q; k++) queries.emplace_back(randRange(1, 10), randRange(1, 10));
        }
        else {
            // 大规模测试 (N=200)
            N = 200; 
            if (i == 7) M = 200; // 稀疏
            else if (i == 8) M = 2000; // 中等
            else M = 10000; // 稠密

            Q = 10000;

            // 构造连通主干
            for(int k=1; k<N; k++) edges.emplace_back(k, k+1, randRange(10, 100));
            
            // 随机加边
            int remain = max(0, M - (N - 1));
            for(int k=0; k<remain; k++) {
                edges.emplace_back(randRange(1, N), randRange(1, N), randRange(1, 100));
            }

            for(int k=0; k<Q; k++) queries.emplace_back(randRange(1, N), randRange(1, N));
        }

        // 写入输入
        fin << N << " " << edges.size() << " " << Q << "\n";
        for (const auto& e : edges) {
            fin << get<0>(e) << " " << get<1>(e) << " " << get<2>(e) << "\n";
        }
        for (const auto& q : queries) {
            fin << q.first << " " << q.second << "\n";
        }

        // 写入输出
        solve(N, (int)edges.size(), Q, edges, queries, fout);

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