思路跟 K 短路一样，然后取最大的情况。

TLE+MLE，数组开一千的话全 RE。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans = -114514;
int etot = 0,Last[5000],Next[100050],End[100050],Len[100050],id[100050];
void addedge(int u,int v,int c,int d){
	etot++;
	Next[etot] = Last[u];
	Last[u] = etot;
	End[etot] = v;
	Len[etot] = c;
	id[etot] = d;
	return;
}
int dis[5000];
bitset<5000> used;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> que1;
void dijkstra(){
	while(que1.size()){
		que1.pop();
	}
	memset(dis,0x3f,sizeof(int)*(n+10));
	used.reset();
	dis[n] = 0;
	que1.push({0,n});
	int now;
	while(que1.size()){
		now = que1.top().second;
		if(used[now] || que1.top().first != dis[now]){
			que1.pop();
			continue;
		}
		que1.pop();
		used[now] = 1;
		for(int i = Last[now]; i; i = Next[i]){
			if(id[i]^1){
				continue;
			}
			if(dis[End[i]] > dis[now]+Len[i]){
				dis[End[i]] = dis[now]+Len[i];
				if(!used[End[i]]){
					que1.push({End[i],dis[End[i]]});
				}
			}
		}
	}
	return;
}
struct node{
	int key,val;
};
bool operator<(node x,node y){
	return x.val+dis[x.key] < y.val+dis[y.key];
}
priority_queue<node> que;
void a_star(){
	while(que.size()){
		que.pop();
	}
	que.push((node){1,0});
	node now;
	while(que.size()){
		now = que.top();
		que.pop();
		if(now.key == n){
			ans = max(ans,now.val);
			continue;
		}
		for(int i = Last[now.key]; i; i = Next[i]){
			if(id[i]){
				continue;
			}
			que.push((node){End[i],now.val+Len[i]});
		}
	}
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= m; i++){
		static int tpa,tpb,tpc;
		scanf("%d%d%d",&tpa,&tpb,&tpc);
		tpa++,tpb++;
		addedge(tpa,tpb,tpc,0);
		addedge(tpb,tpa,tpc,1);
	}
	dijkstra();
	a_star();
	printf("%d",ans);
	return 0;
}