2021 RoboCom CAIP 本科组（初赛）第三题——打怪升级_robocomcaip题目难度

首先这是一道多源最短路径的问题。看网上很多人都是先用一次Floyd再用一次Dijkstra做的这道题，这导致了代码特别长，其实完全没必要，只要一次Floyd就够了。注意学习打印路径的方式，相信这道题学会了之后，对最短路径算法的理解会更进一步的。

先看题干：

 这道题题干很长，请耐心看完，而且题目难度对于初学者来说算是不小了。

这是测试样例：

 注意时间限制：5s，所以还是比较宽松的。 

下面是代码：

#include <bits/stdc++.h>
using namespace std;
 
// n，m含义如题所述，path[i][j]表示i到j的最短路径的下一个节点编号
int n, m, path[1001][1001];
pair<int, int> G[1001][1001]; // 存图，first是能量，second是武器价值
int main() {
    cin >> n >> m;
    // 先初始化，请读者自己分析
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i - j) G[j][i].first = G[i][j].first = INT_MAX, path[i][j] = j;
    // 输入    
    for (int i = 0, u, v, e, w; i < m; i++) {
        cin >> u >> v >> e >> w;
        G[u][v] = G[v][u] = make_pair(e, w);
    }
    // Floyd算法
    for (int k = 1; k <= n; k++)
        for (int i = 1; i < n; i++)
            if (G[i][k].first - INT_MAX) // 能到达
                for (int j = i + 1; j <= n; j++) // 由于是无向图（对称性），不必每都循环n次
                    if (G[k][j].first - INT_MAX) { // 能到达
                        if (G[i][k].first + G[k][j].first < G[i][j].first) // 先按能量求最短的路径
                            G[j][i].first = G[i][j].first = G[i][k].first + G[k][j].first, // 根据对称性，有这样的写法
                            G[j][i].second = G[i][j].second = G[i][k].second + G[k][j].second,
                            path[i][j] = path[i][k], path[j][i] = path[j][k];
                        else if (G[i][k].first + G[k][j].first == G[i][j].first && G[i][k].second + G[k][j].second > G[i][j].second) // 能量一样时按武器价值求最大的路径
                            G[j][i].second = G[i][j].second = G[i][k].second + G[k][j].second,
                            path[i][j] = path[i][k], path[j][i] = path[j][k];
                    }
    int p; // 记录降落点
    for (int i = 1, e = INT_MAX; i <= n; i++) // 开始求降落点，e记录目前耗费能量最大路径的最小能量耗费值
        if (int w = max_element(G[i] + 1, G[i] + n + 1)->first; w < e) e = w, p = i; // 更新
    cout << p << endl;
    int k, t; // 目的地
    cin >> k;
    while (k--) {
        cin >> t;
        int pos = p;
        cout << pos;
        while (path[pos][t]) { // 注意是如何打印路径的
            cout << "->" << path[pos][t];
            pos = path[pos][t];
        }
        cout << endl << G[p][t].first << ' ' << G[p][t].second << endl;
    }
    return 0;
}

下面是提交结果：

 最长时间的也才807ms，可以说轻松通过

有什么不懂的可以在评论区问我，欢迎交流学习~