B-旅行

题目描述

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

输入描述:

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

输出描述:

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

题解

仔细读一下题目的要求，保证三个点一个作为起点，一个作为中转点一个作为终点，在每次从一个点走到另外一个点的时候都走最短路径的情况下的最长距离。那么我们就枚举每一个中转点，计算他到每个点的最短距离，找出最大的两个加起来，在所有的结果里取一个最大的就好啦。不需要担心这三个点重合到一条路上了，因为我们可以自主定义谁是起点谁是终点谁是中转点。比如下图

如果我们定义2为中转点的那答案只能是1到3的距离，但如果我们定义1为中转点的话那答案就是1到2的距离加上1到3的距离。所以我们放心枚举就好啦~

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)

template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
int n,m;
vector<pii> v[N];
int dp[N],mz[N];
int ans=-1;
void dis(int x){
    memset(dp,0x3f,sizeof(dp));
    priority_queue<pii> Q;
    Q.push({0,x});
    dp[x]=0;
    while(!Q.empty()){
        pii now=Q.top();Q.pop();
        for(int i=0,len=v[now.se].size();i<len;++i){
            int to=v[now.se][i].fi;
            if(dp[to]>dp[now.se]+v[now.se][i].se){
                dp[to]=dp[now.se]+v[now.se][i].se;
                Q.push({-dp[to],to});
            }
        }
    }
    int cnt=0;
    for(int i=1;i<=n;++i){
        //cout<<i<<" "<<dp[i]<<endl;
        if(dp[i]!=0x3f3f3f3f){
            mz[++cnt]=dp[i];
        }
    }
    if(cnt>2){
        sort(mz+1,mz+1+cnt);
        ans=max(ans,mz[cnt]+mz[cnt-1]);
    }
}
void solve(){
    n=gn(),m=gn();
    for(int i=1;i<=n;++i){
        v[i].clear();
    }
    for(int i=1;i<=m;++i){
        int a=gn(),b=gn(),c=gn();
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    ans=-1;
    for(int i=1;i<=n;++i){
        dis(i);
    }
    print(ans),putchar(10);
}
////////////////////////////////////////////////////////////////////////
int main(){
    int t;
    t=gn();
    while(t--)
        solve();
}

/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/