题解：P12043 [USTCPC 2025] 图上交互题4 / Constructive Shortest Path

Moonlight_dreams · 2025-05-06 20:30:57 · 题解

题目

代码思路

其实这是一个比较模版的 Floyd 算法的题目。。。

首先，什么是 Floyd

Floyd 就是这是一个图算法，用于求解图中每对顶点之间的最短路径问题。这是一个经典的动态规划算法，用来解决图中任意两个顶点对间最小路径的问题。

解决思路

首先是初始化：

将 dij 数组全部设为无限大，因为我们需要求的是最小路径。然后循环 n 次，每次将 dij_{i,i} 赋值为 1。

接着就是将输入的 dij_{u , v} 和 dij_{v , u} 都设为边权。

接着就是运用 Floyd 算法，计算 dij 数组（计算的公式是 dij[x][y] = min(dij[x][y] , dij[x][k] + dij[k][y]);）。

最后就是输出答案。

AC 代码如下

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505 , M = 1e5 + 5;
int dij[N][N];
struct stu
{
    int x , y , val;
}s[M];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n , m;
    cin >> n >> m;
    memset(dij , 0x3f , sizeof dij);
    for (int i = 1; i <= n; i++)
    {
        dij[i][i] = 0;
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> s[i].x >> s[i].y >> s[i].val;
        int u = s[i].x , v = s[i].y , w = s[i].val;
        dij[u][v] = dij[v][u] = min(dij[u][v] , w);
    }
    for (int k = 1; k <= n; k++)
    {
        for (int x = 1; x <= n; x++)
        {
            for (int y = 1; y <= n; y++)
            {
                dij[x][y] = min(dij[x][y] , dij[x][k] + dij[k][y]);
            }
        }
    }
    for (int i = 1; i <= m; i++)
    {
        if (dij[s[i].x][s[i].y] < s[i].val)
        {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes" << endl;
    for (int i = 1; i <= m; i++)
    {
        cout << s[i].val << " ";
    }
    return 0;
}