链式前向星
(next)指的是上一条同起点边的位置，(to)表示这条边的终点，(val)表示边权。
(u、v、val)分别表示起点，终点，边权。
(head[x])存以(x)为起点的，最后加入的边的位置(edge[head[u]])
struct node{
int next,to,val;
}edge[maxn];
int head[maxn];
int tot=0;
head[x]=-1;//根据这个需要变换遍历链式的方法
void add(int u,int v,int val){
edge[++tot].to=v;
edge[tot].val=val;
edge[tot].next=head[u];
head[u]=tot;
}
dij堆优化
priority_queue<pii,vector<pii >,greater<pii > >qp;
int dis[maxn],vis[maxn];
void dijkstra(int src){
for(int i=1;i<=n;++i){
dis[i]=INF;
}
dis[src]=0;
qp.push({0,src});
while(!qp.empty()){
pii t=qp.top;qp.pop();
int u=t.second;
if(vis[u])continue;
vis[u]=1;
for(int i=head[u];i;i=edge[i].next){
if(dis[edge[i].to]>dis[u]+edge[i].val){
dis[edge[i].to]=dis[u]+edge[i].val;
qp.push({dis[edge[i].to],edge[i].to});
}
}
}
}
链接：https://ac.nowcoder.com/acm/problem/14550
来源：牛客网
题目描述
小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.
思路：
遍历中转点，找出和中转点距离最大的两个地方分别作为起点和终点。
我选择了链式前向星+dij
链式前向星遍历时采用
for(int i=head[u];i;i=edge[i].next){
}
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '
'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<" : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> PII;
const int maxn = 2e5 + 10;
int n,m;
int dis[maxn],vis[maxn];
priority_queue<pii,vector<pii >,greater<pii> >qp;
struct edge{
int next;
int to;
int val;
}edge[maxn];
int head[maxn];
int tot=0;
void add(int u,int v,int val){
edge[++tot].to=v;
edge[tot].val=val;
edge[tot].next=head[u];
head[u]=tot;
}
int dij(int src){
while(!qp.empty())qp.pop();
for(int i=1;i<=n;++i){
dis[i]=INF;vis[i]=0;
}
dis[src]=0;
qp.push({0,src});
int x=0,y=0;
while(!qp.empty()){
pii t=qp.top();qp.pop();
int u=t.second;
if(vis[u])continue;
vis[u]=1;
y=max(y,dis[u]);
if(y>x)swap(x,y);
for(int i=head[u];i;i=edge[i].next){
if(vis[edge[i].to])continue;
if(dis[edge[i].to]>dis[u]+edge[i].val){
dis[edge[i].to]=dis[u]+edge[i].val;
qp.push({dis[edge[i].to],edge[i].to});
}
}
}
if(!y)return 0;
else return x+y;
}
int main(){
int t;cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;++i)head[i]=-1;
int a,b,c;
while(m--){
cin>>a>>b>>c;
add(a,b,c);add(b,a,c);
}
int ans=-1;
for(int i=1;i<=n;++i){
ans=max(dij(i),ans);
}
if(ans)cout<<ans<<endl;
else cout<<-1<<endl;
}
}