0分球条

#include<bits/stdc++.h>
using namespace std;
int v[1005][1005];
int dp[1005];
int q[1005];
int e[1005],cnt;
bool vis[1005];
int n,m;
void dijkstra(int s){
	for(int i=1;i<=n;i++){
		dp[i]=0x3f3f3f3f;
	}
	dp[s]=0;
	for(int i=1;i<=n;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&(t==-1||dp[j]<dp[t])){
				t=j;
			}
		}
		if(t==-1){
			break;
		}
		vis[t]=true;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&v[t][j]!=0x3f3f3f3f&&dp[j]>dp[t]+v[t][j]){
				dp[j]=dp[t]+v[t][j];
				q[j]=t;
			}
		}
	}
}
int dijkstrago1(int s){
	for(int i=1;i<=n;i++){
		dp[i]=0x3f3f3f3f;
		vis[i]=0;
	}
	dp[s]=0;
	for(int i=1;i<=n;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&(t==-1||dp[j]<dp[t])){
				t=j;
			}
		}
		if(t==-1){
			break;
		}
		vis[t]=true;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&v[t][j]!=0x3f3f3f3f&&dp[j]>dp[t]+v[t][j]){
				dp[j]=dp[t]+v[t][j];
			}
		}
	}
	return dp[1];
}
int main(){
	int n,m,xxs=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			v[i][j]=0x3f3f3f3f;
		}
		v[i][i]=0;
	}
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		v[x][y]=min(v[x][y],z);
		v[y][x]=min(v[y][x],z);
	}
	dijkstra(1);
	int c=n;
	while(c!=1){
		e[++cnt]=c;
		c=q[c];
		if(c==0){
			break;
		}
	}
	e[++cnt]=1;
	reverse(e+1,e+cnt+1);
	for(int i=1;i<cnt;i++){
		int x=e[i];
		int y=e[i+1];
		int z=v[x][y];
		v[x][y]=0x3f3f3f3f;
		v[y][x]=0x3f3f3f3f;
		xxs=max(xxs,dijkstrago1(n));
		v[x][y]=z;
		v[y][x]=z;
	}
	cout<<xxs;
	return 0;
}