旅行

题目描述

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

输入描述:

本题包含多组输入，第一行输入一个整数t，表示测试数据的组数
每组测试数据第一行输入两个数N,M表示RRR城一共有的旅游景点的数量，以及RRR城中有的路的数量。
接下来M行，每行三个数，a，b，c表示从a景点和b景点之间有一条长为c的路

输出描述:
每组数据输出两行，
每组数据包含一行，输出一个数，表示整条路程的路长。
如果找不到可行解，输出-1.

思路：
每次选一个点作为中间点，然后跑一边单源最短路，记录距离最远的两个点的距离和，答案就是最大的和，复杂度n n logn
附代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5;
const int INF = 0x3f3f3f3f;
int n,m,s,t;
struct edge{int v,w;edge(int x,int y){v=x,w=y;}};
vector<edge>v[N];
int vis[N],dis[N];
struct node{
    int num,dis;
    node(int x,int y){num=x,dis=y;};
    friend bool operator >(const node &a,const node &b){return a.dis>b.dis;}
};
void add(int x,int y,int z){
    v[x].push_back(edge(y,z));
}
ll Dig(int s){
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    priority_queue<node,vector<node> ,greater<node> >q;
    q.push(node(s,0));
    int x=0,y=0;
    while(!q.empty()){
        node now=q.top();
        q.pop();
        int u=now.num;
        if(vis[u])continue;
        y=max(y,dis[u]);
        if(y>x)swap(x,y);
        vis[u]=1;
        for(int i=0;i<v[u].size();i++){
            edge next=v[u][i];
            if(vis[next.v])continue;
            if(dis[u]+next.w<dis[next.v]){
                dis[next.v]=dis[u]+next.w;
                q.push(node(next.v,dis[next.v]));
            }
        }
    }
    if(!y)return 0;
    return (x+y);
}
void solve(){
    memset(v,0,sizeof(v));
    ll ans=0;
    cin>>n>>m;
    int x,y,z;
    for(int i=0;i<m;i++)
        cin>>x>>y>>z,add(x,y,z),add(y,x,z);
    for(int i=1;i<=n;i++){
        ans=max(Dig(i),ans);
    }
    if(!ans)ans=-1;
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve();
}