链接：https://ac.nowcoder.com/acm/problem/14352 来源：牛客网

题目描述 小z放假了，准备到RRR城市旅行，其中这个城市有N个旅游景点。小z时间有限，只能在三个旅行景点进行游玩。小明租了辆车，司机很善良，说咱不计路程，只要你一次性缴费足够，我就带你走遍RRR城。 小z很开心，直接就把钱一次性缴足了。然而小z心机很重，他想选择的路程尽量长。 然而司机也很聪明，他每次从一个点走到另外一个点的时候都走最短路径。 你能帮帮小z吗？ 需要保证这三个旅行景点一个作为起点，一个作为中转点一个作为终点。（一共三个景点，并且需要保证这三个景点不能重复）.

采用的算法为堆优化的dijkstra算法，分别遍历每一个中转点，找到用算法处理后距离该中转点距离最远的两个点作为起点和终点。

注意事项：1，数组的大小问题2，题目描述为稀疏图，故采取邻接表来储存图（注意邻接表的数组大小）。 经验分享： 1，邻接表中e[],ne[]的大小应该是边的个数，定为点的个数的二倍较好。2，初始化边的长度为正无穷，可采用memset(dis,0x3f,sizeof(dis)),最好保证设定的正无穷的值大于最大边长度的二倍。


#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;

typedef pair<int, int> PII;

int h[N],e[2*N],ne[2*N],w[2*N],dis[N];
//虽然题目描述为M<=1000，但是如果数组设定为N大小的话，会越界导致超时
int n,m,t,idx;
bool st[N];

void add(int a,int b,int c)//插入操作
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}

int dijkstra(int i)//采用堆优化的·dijkstra算法
{
    int max1=0,max2=0;//用max1，max2存储最长的两条路径
    memset(dis,0x3f,sizeof(dis));
    dis[i]=0;
    
    priority_queue<PII,vector<PII>,greater<PII>> heap;//设定为小根堆
    heap.push({0,i});
    
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        
        int distance=t.first,ver=t.second;
        if(st[ver])continue;
        st[ver]=true;
        max2=max(max2,dis[ver]);
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>distance+w[i])
            {
                dis[j]=distance+w[i];
                heap.push({dis[j],j});
            }
        }
        if(max2>max1)swap(max1,max2);
    }
    for(int i=1;i<=n;i++) st[i]=false;
    if(max2==0)return -1;
    else return max1+max2;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(h,-1,sizeof(h));
        scanf("%d%d",&n,&m);
        while(m--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c),add(b,a,c);//题目描述不明白，城市之间应该是无向图，故插入两次
        }
        int x=-1;
        for(int i=1;i<=n;i++)
        {
            x=max(dijkstra(i),x);
        }
        printf("%d\n",x);
        idx=0;
    }
    return 0;
}