提出 #62138147

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int n, m, s, t;
vector<vector<int>> to;
bool check()
{
    if (m != n - 1)
        return true;
    int mx = 0;
    for (int i = 1; i <= n; ++i)
        mx = max(mx, (int)to[i].size());
    return mx > 2;
}
void bfs(int s, vector<bool> &ban, vector<int> &dis, vector<int> &pre)
{
    for (int i = 1; i <= n; ++i)
    {
        dis[i] = inf;
    }
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int v : to[u])
        {
            if (ban[v])
                continue;
            if (dis[v] > dis[u] + 1)
            {
                dis[v] = dis[u] + 1;
                q.push(v);
                pre[v] = u;
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s >> t;
    to.resize(n + 1);
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        to[u].push_back(v);
        to[v].push_back(u);
    }

    vector<int> dis(n + 1), dis2(n + 1), dis3(n + 1);
    vector<int> pre(n + 1);
    vector<bool> ban(n + 1);
    bfs(s, ban, dis, pre);

    vector<bool> in_road(n + 1);
    vector<int> road;
    for (int i = t; i != s; i = pre[i])
    {
        road.push_back(i);
        in_road[i] = true;
    }
    in_road[s] = true;
    road.push_back(s);

    ban[t] = true;
    bfs(s, ban, dis2, pre);
    ban[t] = false;
    ban[s] = true;
    bfs(t, ban, dis3, pre);
    ban[s] = false;
    int ans = inf;
    for (int v = 1; v <= n; ++v)
        if (!in_road[v] && dis2[v] != inf && dis3[v] != inf)
        {
            ans = min(ans, dis[t] + dis2[v] + dis3[v]);
        }

    for (int v = 1; v <= n; ++v)
        if (!in_road[v])
        {
            for (int vv : to[v])
                if (vv != s && vv != t && in_road[vv])
                    ans = min(ans, dis[t] * 2 + 2);
        }

    for (int u = 1; u <= n; ++u)
        if (u != s && u != t && in_road[u])
            ban[u] = true;

    vector<int> deg(n + 1);
    for (int u = 1; u <= n; ++u)
        for (int v : to[u])
            if (!(in_road[u] && in_road[v]))
            {
                ++deg[u];
            }

    {
        ban[t] = true;
        bfs(s, ban, dis2, pre);
        ban[t] = false;
        ban[s] = true;
        bfs(t, ban, dis3, pre);
        ban[s] = false;
        int x = inf, y = inf;
        for (int u = 1; u <= n; ++u)
            if (dis2[u] != inf && deg[u] >= 3)
            {
                x = min(x, dis2[u]);
            }
        if (deg[s] >= 2)
            x = 0;
        for (int u = 1; u <= n; ++u)
            if (dis3[u] != inf && deg[u] >= 3)
            {
                y = min(x, dis3[u]);
            }
        if (deg[t] >= 2)
            y = 0;
        int z = min(x, y);
        if (z != inf)
        {
            ans = min(ans, 2 * dis[t] + (z + 1) * 4);
        }
    }
    if (ans == inf)
        ans = -1;
    cout << ans << '\n';
}

/*
1. 检查图是否是一条链，如果是，输出-1
2.
先取一条s到t的最短路径，设路径为
s,u1,u2,...,uk,t

3. 先考虑走两条不同路径的情况：
对于一个点v，v不属于这条路径上的点
那么经过点v需要的步数是 dis(s,t)+dis2(s,v)+dis3(v,t)
注意：dis2(s,v)不能经过点t，即删掉点t再做最短路计算
注意：dis3(v,t)不能经过点s，即删掉点s再做最短路计算
在所有点v中去取这个距离最小的即可

4. 如果存在一个点v，v不属于这条路径上的点，且v与u1,u2,...,uk中任意一个点相邻
则答案和2+2dis(s,t)取min

5.
删除点u1,u2,...,uk后
如果点s和点t不在一个连通块：
设x为点s走到的第一个度数>=3的点的距离（没有就是inf)
设y为点t走到的第一个度数>=3的店的距离（没有就是inf）
设 z=min(x,y)
答案和2dis(s,t)+4(z+1)取min


4 3 2 3
1 2
2 3
2 4
*/

提出情報

ジャッジ結果