【dij】旅行

我会带着你远行 2024-03-24 09:19 56阅读 0赞

[1004-旅行\_2021秋季算法入门班第九章习题：图论（重现赛）@lamentropetion (nowcoder.com)][1004-_2021_lamentropetion _nowcoder.com]

题意：

![105d3a3f243b439b96975ba893c5351e.png][]

思路：

dij的时间复杂度是O(mlogm)

因此可以枚举其中间点，然后每次枚举的点都做一遍dij，取最长的两条边即可

注意特判不连通的情况

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    using i64 = long long;
    const int mxn=1e3+10;
    const int mxe=1e3+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    struct ty{
        int to,next,w;
    }edge[mxe<<1];
    struct ty2{
        int x,dis;
        bool operator<(const ty2&a )const{
            return a.dis<dis;
        }
    };
    
    priority_queue<ty2> q;
    int n,m,u,v,w,tot=0,ans;
    int head[mxn],dis[mxn],vis[mxn];
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void dij(int s){
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        dis[s]=0;
        q.push({s,0});
        while(!q.empty()){
            ty2 u=q.top();
            q.pop();
            if(vis[u.x]) continue;
            vis[u.x]=1;
            for(int i=head[u.x];~i;i=edge[i].next){
                if(dis[edge[i].to]>dis[u.x]+edge[i].w){
                    dis[edge[i].to]=dis[u.x]+edge[i].w;
                    q.push({edge[i].to,dis[edge[i].to]});
                }
            }
        }
        sort(dis+1,dis+1+n,greater<int>());
        int cnt=0,res=0;
        for(int i=1;i<=n;i++){
            if(dis[i]==0) continue;
            if(dis[i]>=Inf) continue;
            cnt++;
            res+=dis[i];
            if(cnt>=2) break;
        }
        if(res<Inf&&cnt==2) ans=max(ans,res);
    }
    void G_init(){
        tot=0;
        ans=-1;
        for(int i=0;i<=n;i++){
            head[i]=-1;
        }
    }
    void solve(){
        cin>>n>>m;
        G_init();
        for(int i=1;i<=m;i++){
            cin>>u>>v>>w;
            add(u,v,w);
            add(v,u,w);
        }
        for(int i=1;i<=n;i++) dij(i);
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[1004-_2021_lamentropetion _nowcoder.com]: https://ac.nowcoder.com/acm/contest/54497/1004
[105d3a3f243b439b96975ba893c5351e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/a0f49aa56e214f6b91a09e87c765fa18.png