dij+堆优化+深搜路径编号

#include<bits/stdc++.h>
#define Cysy ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define m_p(a,b) make_pair(a,b) 
#define inf 1e9
#define int long long
using namespace std;
const int N=1005;
int n,m,ans[N],f[N];
bool vis[N],vis1[N][N];
vector<pair<int,int> > A[N];
void dijsktra(){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
	for(int i=1;i<=n;i++)vis[i]=0;
	for(int i=1;i<=n;i++)ans[i]=inf;
	ans[n]=0;
	q.push(m_p(ans[n],n));
	while(!q.empty()){
		int fst=q.top().second;
		q.pop();
		if(vis[fst])continue;
		vis[fst]=1;
		for(int i=0;i<A[fst].size();i++){
			int v=A[fst][i].first;
			int w=A[fst][i].second;
			if(vis1[fst][v])continue;
			if(ans[fst]+w<ans[v]){
				ans[v]=ans[fst]+w;
				q.push(m_p(ans[v],v));
			}
		}
	}
	return ;
}
bool p=0;
int now=0;
void dfs(int k){
	f[++now]=k;
	if(k==n||p){p=1;return ;}
	for(int i=0;i<A[k].size();i++){
		int v=A[k][i].first;
		int w=A[k][i].second;
		if(ans[k]==ans[v]+w){
			dfs(v);
		}
	}
}
signed main(){
	Cysy;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		A[u].push_back(m_p(v,w));
		A[v].push_back(m_p(u,w));
	}
	dijsktra();
	dfs(1);
	++now;
	int cnt=-1e9;
	while(--now){
		if(now==1)break;
		int u=f[now],op;
		int v=f[now-1],op1;
		int w=A[u][op].second;
		vis1[u][v]=vis1[v][u]=1;
		dijsktra();
		vis1[u][v]=vis1[v][u]=0;
		if(ans[1]>cnt){
			cnt=ans[1];
		}
	}
	cout<<cnt;
	return 0;
}