【dij】旅行

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

题意：

思路：

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

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

注意特判不连通的情况

Code：

#include 
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 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 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>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<>__;while(__--)solve();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！