Rt，知道应该没人会来帮我，但还是放一下吧

要是×姐真的来了呢

思路：Tarjan缩点+Dijkstra跑一遍最短路

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=1e6+5,INF=2147483647;
struct node{
	int next,to,dis;
}Edge1[M],Edge[M];
struct Pair{
	int dis,now;
	bool operator <(const Pair &x)	const
	{
		return x.dis>dis;
	}
};
int head[N],head1[N],low[N],dis[N],dfn[N],belong[N];
int w[N],u[N],v[N];
int n,m,cnt,tot,num,tot1;
bool vis[N],Vis[N];
stack<int> s;
inline int read()
{
	int x=0;
	bool w=0;
	char c=getchar();
	while(!isdigit(c))
		w|=c=='-',c=getchar();
	while(isdigit(c))
		x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void add(int u,int v,int w)
{
	Edge[++tot].to=v;
	Edge[tot].dis=w;
	Edge[tot].next=head[u];
	head[u]=tot;
}
inline void add_Tarjan(int u,int v,int w)
{
	Edge1[++tot1].to=v;
	Edge1[tot1].next=head1[u];
	Edge1[tot1].dis=w;
	head1[u]=tot1;
}
inline void Tarjan(int u)
{
	low[u]=dfn[u]=++num;
	s.push(u);
	vis[u]=1;
	for(register int i=head1[u];i;i=Edge1[i].next)
	{
		int v=Edge1[i].to;
		if(!dfn[v])
		{
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else
		{
			if(vis[v])
				low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u])
	{
		++cnt;
		int t=0;
		while(t!=u)
		{
			t=s.top();
			s.pop();
			vis[t]=0;
			belong[t]=cnt;
		}
	}
}
inline void Dijkstra()
{
	for(register int i=1;i<=cnt;++i)
		dis[i]=INF;
	dis[1]=0;
	priority_queue<Pair> q;
	q.push((Pair){0,1});
	while(!q.empty())
	{
		int u=q.top().now;
//		cout<<u<<" u\n";
		q.pop();
		if(Vis[u])	continue;
		Vis[u]=1;
//		cout<<"OK_VIS:"<<u<<endl;
//		cout<<head[u]<<" head[u]\n";
		for(register int j=head[u];j;j=Edge[j].next)
		{
			int v=Edge[j].to,w=Edge[j].dis;
//			cout<<v<<" v\n";
			if(dis[u]+w<dis[v])	
			{
//				cout<<"OK u:"<<u<<" v:"<<v<<" w:"<<w<<endl;
				dis[v]=dis[u]+w;
				q.push((Pair){dis[v],v});
			}
		}
	}
}
signed main()
{
	n=read(),m=read();
	for(register int i=1;i<=m;++i)
	{
		u[i]=read(),v[i]=read(),w[i]=read();
		add_Tarjan(u[i],v[i],w[N]);
	}
//	for(register int i=1;i<=m;++i)
//	{
//		int u=read(),v=read(),w=read();
//		add_Tarjan(u,v,w);
//	}
//	for(register int i=1;i<=m;++i)
//		cout<<Edge1[i].to<<' '<<endl;
	for(register int i=1;i<=n;++i)
		if(!dfn[i])	Tarjan(i);
//	cout<<n<<' '<<cnt<<endl;
//	for(register int i=1;i<=cnt;++i)
//		for(register int j=head1[i];j;j=Edge1[j].next)
//		{
//			int v=Edge1[j].to,w=Edge1[j].dis;
//			if(belong[i]!=belong[v])
//				add(belong[i],belong[v],w);
//			cout<<i<<' '<<v<<" i v\n";
//		}
	for(register int i=1;i<=m;++i)
	{
		if(belong[u[i]]!=belong[v[i]])
			add(belong[u[i]],belong[v[i]],w[i]);
	}
//	for(register int i=1;i<=cnt;++i)
//		for(register int j=head[i];j;j=Edge[j].next)
//			cout<<i<<' '<<Edge[j].to<<' '<<Edge[i].dis<<endl;cout<<endl;
//	for(register int i=1;i<=tot;++i)
//		 cout<<Edge[i].to<<' '<<"Edge\n";
	Dijkstra();
	printf("%d",dis[cnt]);
	return 0;
}

代码有点杂，注释不用看