Oiclass P1959. 分糖果 题解

· · 题解

这道题非常的水。

虽然是dijkstra算法，但是这里DFS是线性的 O(n)。

所以，我们可以直接DFS。

先放AC代码：

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
vector <int> v[N];
int n,m,ans,p,c,cnt,d[N];
bool vis[N];

void dfs(int x,int Time)
{
    d[x] = min(d[x],Time);
    for(int p : v[x])
        if (d[p] > Time + 1)
        {
            d[p] = Time + 1;
            dfs(p,Time + 1);
        }
}

int main()
{
    memset(d,0x3f,sizeof(d));
    ios::sync_with_stdio(0);
    cin >> n >> p >> c;
    cin >> m;
    while (p --)
    {
        int x,y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    vis[c] = 1;
    dfs(c,1);
    for(int i = 1;i <= n;i ++) ans = max(ans,d[i]);
    cout << ans + m << endl;
    return 0;
}

这个就没什么好说的了。首先我们从 c 开始DFS。这里要注意初始时间为 1。然后我们要使用记忆化搜索。当搜过去的答案比原来的答案更优，我们就继续DFS下去。最后就输出最大值 + m 就可以了。