[补题] 西南民族大学第十二届程序设计竞赛C题 最长的最短路

传送门

题意: 找0到所有点中最短路的最长的一个

(可能会点达不到)

直接跑spfa

因为不会spfa 还提前了解了bellman-ford

/***
for( n )
    for(所有边)
    a->b a,b,w

随便存边
dis[b] = min (dis[b],dis[a]+w)
松弛操作

可以看出 bellman-ford 类似直接暴力

循环n次之后一定满足
dis[b] dist[t] + w[i])
            {

                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    int t = spfa();

    int maxn  = 0;
    int mp  =0;
    for(int i=n;i>=1;i--)
    {
        if(dist[i]>=maxn)
            maxn =dist[i],mp=i;
    }
    cout