2022赛前模测 提高组验题- 18

问题 B: 【2022NOIP联测2 10月2日】最短路问题 V3

我把我写的这个改了改格式去最短路的专题里都能A某些东西，比如：信使，对，这题的数据很水，但是我把它交到accoders上不是T了而是错了！！WA 20……这有点离谱？然后注释掉的就是这个B的错误写法：有大佬知道它为什么不对吗***

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 500;
const ll inf = 1e17;

int n, m, q, ff[maxn], stk[maxn], cnt, id[maxn];
ll ans, dis[maxn];
bool vis[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
struct node 
{
    int next, to, w;
}a[maxn<<1], e[maxn<<1];
int len, tot, head[maxn], h[maxn];
void add(int x, int y, int w)
{
    a[++len].to = y; a[len].next = head[x]; a[len].w = w;
    head[x] = len;
}
void add_tree(int x, int y, int w)
{
    e[++tot].to = y; e[tot].next = h[x]; e[tot].w = w;
    h[x] = tot;
}
inline void New(int x) {if(id[x]) return; stk[++cnt] = x; id[x] = cnt;}
int fa[maxn], dep[maxn], siz[maxn], son[maxn], top[maxn];
void find_heavy_edge(int u, int fat, int depth)
{
    //printf("u = %d\n", u);
    fa[u] = fat;
    dep[u] = depth;
    siz[u] = 1;
    son[u] = 0;
    int maxsize = 0;

    for(int i=h[u]; i; i=e[i].next)
    {
        int v = e[i].to;
        if(dep[v]) continue;
        dis[v] = dis[u] + e[i].w;
        find_heavy_edge(v, u, depth+1);
        siz[u] += siz[v];
        if(siz[v] > maxsize)
        {
            maxsize = siz[v];
            son[u] = v;
        }
    }
}
void connect_heavy_edge(int u, int ancestor)
{
    top[u] = ancestor;
    if(son[u])
    {
        connect_heavy_edge(son[u], ancestor);
    }
    for(int i=h[u]; i; i=e[i].next)
    {
        int v = e[i].to;
        if(v == son[u] || v == fa[u]) continue;
        connect_heavy_edge(v, v);
    }
}
int LCA(int x, int y)
{
    while(top[x] != top[y])
    {
        if(dep[x] < dep[y]) swap(x, y);
        x = fa[top[x]];
        //printf("x = %d y = %d\n", x, y);
    }
    if(dep[x] > dep[y]) swap(x, y);
    return x;
}
int find(int x)
{
    if(x == ff[x]) return x;
    return ff[x] = find(ff[x]);
}
queue<int> qu;
ll d[44][maxn];
void spfa(int st)
{
    for(int i=1; i<=n; i++) d[id[st]][i] = inf;
    d[id[st]][st] = 0;
    vis[st] = 1;
    qu.push(st);
    while(!qu.empty())
    {
        int x = qu.front(); qu.pop();
        vis[x] = 0;
        for(int i=head[x]; i; i=a[i].next)
        {
            int y = a[i].to;
            if(d[id[st]][y] > d[id[st]][x] + a[i].w)
            {
                d[id[st]][y] = d[id[st]][x] + a[i].w;
                if(!vis[y])
                {
                    vis[y] = 1; qu.push(y);
                }
            }
        }
    }
}

int main()
{
    //freopen("1.in", "r", stdin);
    n = read(); m = read();
    for(int i=1; i<=n; i++) ff[i] = i;
    for(int i=1; i<=m; i++)
    {
        int u = read(), v = read(), w = read();
        add(u, v, w); add(v, u, w);
        int fx = find(u), fy = find(v);
        if(fx == fy) 
        {
            New(u); New(v);
            continue;
        }
        ff[fx] = fy;
        add_tree(u, v, w); add_tree(v, u, w);
    }
    find_heavy_edge(1, 0, 1);
    connect_heavy_edge(1, 1);
    for(int i=1; i<=cnt; i++)
    {
        spfa(stk[i]);
    }
    /*q = read();
    while(q--)
    {
        int u = read(), v = read();
        int lca = LCA(u, v);
        ans = dis[u] + dis[v] - dis[lca] - dis[lca];
        for(int i=1; i<=cnt; i++)
        {
            ans = min(ans, d[i][u]+d[i][v]);
        }
        printf("%lld\n", ans);
    }*/
    ll res = 0;
    for(int i=2; i<=n; i++)
    {
        int lca = LCA(1, i);
        res = dis[i] - dis[lca] - dis[lca];
        for(int j=1; j<=cnt; j++)
        {
            res = min(res, d[j][1]+d[j][i]);
        }
        //printf("res[%d] = %lld\n", i, res);
        ans = max(ans, res);
    }
    printf("%lld\n", ans);
    
    return 0;
}