题解：CF2172M Maximum Distance To Port

AA12_G · 2025-12-05 22:24:38 · 题解

思路

按照题意模拟即可，使用广度优先搜索求最短路即可。

代码

#include <bits/stdc++.h>
using namespace std;
vector <int> mp[214514], v[214514];
int dis[214514];
int n, m, k;
int vis[214514];
int main()
{
    cin >> n >> m >> k;
    //输入
    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        mp[x].push_back (i);
    }//统计每个货物都有哪个地儿弄，下面统计答案用
    for (int i = 1; i <= m; i ++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back (y);
        v[y].push_back (x);
    }//建边
    queue <int> q;
    q.push(1);
    vis[1] = 1;
    while (q.size())
    {
        int t = q.front ();
        q.pop();
        for (auto i : v[t])
        {
            if (!vis[i])
            {
                dis[i] = dis[t] + 1;
                vis[i] = 1;
                q.push(i);
            }
        }
    }//bfs求最短路
    for (int i = 1; i <= k; i ++)
    {
        int maxx = 0;
        for (auto j : mp[i])
        {
            maxx = max (maxx, dis[j]);
        }
        cout << maxx << " ";
    }//统计答案，输出
}