spfa+链式前向星存图

题目大意

首先要明确，不管题目给了多少个城市，题目只需要求三个点之间的最大距离的最短路径，所以我们依次枚举每个中点，让每个点都做一次中点，并跑一次spfa，求出最短路径，然后再求最短路径的最大值就行

细节处理

就是在跑完spfa之后，此时的最短路已经形成，我们所要做的就是求当前节点路径的最大值，并返回，如果没有那就返回-1，在for循环中，如果有多个if那么只要满足if条件里面的语句，那么就执行if语句（除非遇到continue，或者break跳出循环），如果是if...else那么直需要执行其中一条满足的语句就会跳出循环不会执行后面的语句

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
const int inf = 0x3f3f3f3f;
int head[maxn], cnt, dis[maxn], vis[maxn], n, m;
queue<int> q;
struct node
{
    int to, cost, next;
} w[maxn << 1];

void add(int a, int b, int c) //链式前向星存图
{
    w[++cnt].to = b;
    w[cnt].cost = c;
    w[cnt].next = head[a];
    head[a] = cnt;
}
int spfa(int x)
{
    memset(dis, inf, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[x] = 0; //标记起点
    vis[x] = 1;
    q.push(x);
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        vis[v] = 0;
        for (int i = head[v]; ~i; i = w[i].next) //依次遍历该节点的邻接点
        {
            node e = w[i];
            if (dis[e.to] > e.cost + dis[v]) //松弛操作
            {
                dis[e.to] = e.cost + dis[v];
                if (!vis[e.to]) //如果该结点没有被访问过就加入该节点
                {
                    q.push(e.to);
                    vis[e.to] = 1; //标记这个点
                }
            }
        }
    }
    int ma1 = -1, ma2 = -1;
    dis[x] = -3;
    for (int i = 1; i <= n; ++i) //遍历找出最大的和第二大的边——求和
    {
        if (dis[i] == inf)
            continue;
        if (dis[i] > ma1)
            ma2 = ma1, ma1 = dis[i];
        else if (dis[i] > ma2)
            ma2 = dis[i];
    }
    if (ma1 != -1 && ma2 != -1)
        return ma1 + ma2;
    return -1;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        cnt = 0;
        memset(head, -1, sizeof(head));
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; ++i)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c); //无向图加边两次
            add(b, a, c);
        }
        int ans = -1;
        for (int i = 1; i <= n; ++i)
            ans = max(ans, spfa(i));
        printf("%d\n", ans);
    }
    return 0;
}