//同求+0x7fffffff
```cpp
#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
re int an=0;
re char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c)){an=(an<<1)+(an<<3)+c-'0';c=getchar();}
return an;
}
struct node{int x,dis;}heap[1000010],v;
int n,m,cnt,size,dis[200010],low[200010],dfn[200010],linked[200010];
int x,y,z,tot,first[200010],next[1000010],to[1000010],w[1000010];
bool vis[200010];
stack<int>st;
bool cmp(node a,node b){return a.dis>b.dis;};
void in(node a){
heap[++size]=a;
push_heap(heap+1,heap+1+size,cmp);
}
node out(){
pop_heap(heap+1,heap+1+size,cmp);
return heap[size--];
}
void addedge(int x,int y,int z){
to[++tot]=y;
next[tot]=first[x];
w[tot]=z;
first[x]=tot;
}
void tarjan(int k){
st.push(k);
low[k]=dfn[k]=++cnt;
vis[k]=1;
for(re int i=first[k];i;i=next[i]){
if(!dfn[to[i]]){
tarjan(to[i]);
low[k]=min(low[k],low[to[i]]);
}
else if(vis[to[i]])
low[k]=min(low[k],low[to[i]]);
}
if(low[k]!=dfn[k])return;
linked[k]=++tot;
while(!st.empty()&&st.top()!=k){
linked[st.top()]=tot;
st.pop();
}
st.pop();
}
int main(){
n=read(),m=read();
for(re int i=1;i<=m;i++){
x=read(),y=read(),z=read();
addedge(x,y,z);
}
tot=0;
tarjan(1);
for(re int i=1;i<=n;i++)
for(re int j=first[i];j;j=next[j])
if(linked[i]==linked[to[j]])
w[j]=0;
memset(vis,0,sizeof(vis));
memset(dis,0x7f,sizeof(dis));
dis[1]=0;
in((node){1,0});
while(size){
while(vis[v.x]&&size)v=out();
vis[v.x]=1;
for(re int i=first[v.x];i;i=next[i]){
if(dis[v.x]+w[i]<dis[to[i]]){
dis[to[i]]=dis[v.x]+w[i];
if(!vis[to[i]])
in((node){to[i],dis[to[i]]});
}
}
}
printf("%d",dis[n]);
return 0;
}
```
by 天朝理科生 @ 2019-02-16 11:01:56
+1
by village_lamp @ 2019-08-28 20:13:46
+1
by zs12138 @ 2019-09-03 18:26:55