#include<bits/stdc++.h>
using namespace std;
const int MAX = 200100;
const int MAX_M = 1000100;
typedef pair<int,int> PII;```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAX = 200100;
const int MAX_M = 1000100;
typedef pair<int,int> PII;
set<PII> cq;
int n,m,u,v,l,bh,idx,top,scc,bh2;
int p[MAX],low[MAX],dfn[MAX],S[MAX],belong[MAX],p2[MAX],dis[MAX];
bool in_s[MAX];
struct jgt{
int v,l,next;
}E[MAX_M],E2[MAX_M];
void init()
{
memset(p,-1,sizeof(p));
memset(p2,-1,sizeof(p2));
memset(dis,0x3f,sizeof(dis));
}
void insert(int u,int v,int l)
{
E[bh].l=l;
E[bh].v=v;
E[bh].next=p[u];
p[u]=bh++;
}
void insert2(int u,int v,int l)
{
E2[bh2].v=v;
E2[bh2].l=l;
E2[bh2].next=p2[u];
p2[u]=bh2++;
}
void tarjan(int u)
{
dfn[u]=low[u]=++idx;
S[top++]=u;
in_s[u]=true;
for(int i=p[u];~i;i=E[i].next)
{
int v=E[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(in_s[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
scc++;
while(S[top]!=u)
{
belong[S[--top]]=scc;
in_s[S[top]]=false;
}
}
}
void spfa(int st,int en)
{
bool in_q[MAX];
queue<int> q;
q.push(st);
dis[st]=0;
in_q[st]=true;
while(!q.empty())
{
int point = q.front();
q.pop();
in_q[point]=false;
for(int i=p2[point];~i;i=E2[i].next)
{
int v=E2[i].v,l=E2[i].l;
if(dis[point]+l<dis[v])
{
dis[v]=dis[point]+l;
if(!in_q[v])
{
q.push(v);
in_q[v]=true;
}
}
}
}
}
int main()
{
cin>>n>>m;
init();
for(int i=1;i<=m;i++)
{
cin>>u>>v>>l;
insert(u,v,l);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
tarjan(i);
}
}
// for(int i=1;i<=n;i++)
// {
// cout<<i<<" "<<belong[i]<<endl;
// }
int start=belong[1],end=belong[n];
int v,new_u,new_v,len;
for(int i=1;i<=n;i++)
{
for(int id=p[i];~id;id=E[id].next)
{
v=E[id].v,len=E[id].l;
new_u=belong[i],new_v=belong[v];
if(new_u!=new_v&&!cq.count(make_pair(new_u,new_v)) )
{
insert2(new_u,new_v,len);
cq.insert(make_pair(new_u,new_v));
}
}
}
if(start==end)
{
cout<<0;
return 0;
}
spfa(start,end);
cout<<dis[end];
return 0;
}
```
set<PII> cq;
int n,m,u,v,l,bh,idx,top,scc,bh2;
int p[MAX],low[MAX],dfn[MAX],S[MAX],belong[MAX],p2[MAX],dis[MAX];
bool in_s[MAX];
struct jgt{
int v,l,next;
}E[MAX_M],E2[MAX_M];
void init()
{
memset(p,-1,sizeof(p));
memset(p2,-1,sizeof(p2));
memset(dis,0x3f,sizeof(dis));
}
void insert(int u,int v,int l)
{
E[bh].l=l;
E[bh].v=v;
E[bh].next=p[u];
p[u]=bh++;
}
void insert2(int u,int v,int l)
{
E2[bh2].v=v;
E2[bh2].l=l;
E2[bh2].next=p2[u];
p2[u]=bh2++;
}
void tarjan(int u)
{
dfn[u]=low[u]=++idx;
S[top++]=u;
in_s[u]=true;
for(int i=p[u];~i;i=E[i].next)
{
int v=E[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(in_s[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
scc++;
while(S[top]!=u)
{
belong[S[--top]]=scc;
in_s[S[top]]=false;
}
}
}
void spfa(int st,int en)
{
bool in_q[MAX];
queue<int> q;
q.push(st);
dis[st]=0;
in_q[st]=true;
while(!q.empty())
{
int point = q.front();
q.pop();
in_q[point]=false;
for(int i=p2[point];~i;i=E2[i].next)
{
int v=E2[i].v,l=E2[i].l;
if(dis[point]+l<dis[v])
{
dis[v]=dis[point]+l;
if(!in_q[v])
{
q.push(v);
in_q[v]=true;
}
}
}
}
}
int main()
{
cin>>n>>m;
init();
for(int i=1;i<=m;i++)
{
cin>>u>>v>>l;
insert(u,v,l);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
tarjan(i);
}
}
// for(int i=1;i<=n;i++)
// {
// cout<<i<<" "<<belong[i]<<endl;
// }
int start=belong[1],end=belong[n];
int v,new_u,new_v,len;
for(int i=1;i<=n;i++)
{
for(int id=p[i];~id;id=E[id].next)
{
v=E[id].v,len=E[id].l;
new_u=belong[i],new_v=belong[v];
if(new_u!=new_v&&!cq.count(make_pair(new_u,new_v)) )
{
insert2(new_u,new_v,len);
cq.insert(make_pair(new_u,new_v));
}
}
}
if(start==end)
{
cout<<0;
return 0;
}
spfa(start,end);
cout<<dis[end];
return 0;
}
by EternalArthorn @ 2019-03-28 21:45:14
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAX = 200100;
const int MAX_M = 1000100;
typedef pair<int,int> PII;
set<PII> cq;
int n,m,u,v,l,bh,idx,top,scc,bh2;
int p[MAX],low[MAX],dfn[MAX],S[MAX],belong[MAX],p2[MAX],dis[MAX];
bool in_s[MAX];
struct jgt{
int v,l,next;
}E[MAX_M],E2[MAX_M];
void init()
{
memset(p,-1,sizeof(p));
memset(p2,-1,sizeof(p2));
memset(dis,0x3f,sizeof(dis));
}
void insert(int u,int v,int l)
{
E[bh].l=l;
E[bh].v=v;
E[bh].next=p[u];
p[u]=bh++;
}
void insert2(int u,int v,int l)
{
E2[bh2].v=v;
E2[bh2].l=l;
E2[bh2].next=p2[u];
p2[u]=bh2++;
}
void tarjan(int u)
{
dfn[u]=low[u]=++idx;
S[top++]=u;
in_s[u]=true;
for(int i=p[u];~i;i=E[i].next)
{
int v=E[i].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(in_s[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])
{
scc++;
while(S[top]!=u)
{
belong[S[--top]]=scc;
in_s[S[top]]=false;
}
}
}
void spfa(int st,int en)
{
bool in_q[MAX];
queue<int> q;
q.push(st);
dis[st]=0;
in_q[st]=true;
while(!q.empty())
{
int point = q.front();
q.pop();
in_q[point]=false;
for(int i=p2[point];~i;i=E2[i].next)
{
int v=E2[i].v,l=E2[i].l;
if(dis[point]+l<dis[v])
{
dis[v]=dis[point]+l;
if(!in_q[v])
{
q.push(v);
in_q[v]=true;
}
}
}
}
}
int main()
{
cin>>n>>m;
init();
for(int i=1;i<=m;i++)
{
cin>>u>>v>>l;
insert(u,v,l);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
tarjan(i);
}
}
// for(int i=1;i<=n;i++)
// {
// cout<<i<<" "<<belong[i]<<endl;
// }
int start=belong[1],end=belong[n];
int v,new_u,new_v,len;
for(int i=1;i<=n;i++)
{
for(int id=p[i];~id;id=E[id].next)
{
v=E[id].v,len=E[id].l;
new_u=belong[i],new_v=belong[v];
if(new_u!=new_v&&!cq.count(make_pair(new_u,new_v)) )
{
insert2(new_u,new_v,len);
cq.insert(make_pair(new_u,new_v));
}
}
}
if(start==end)
{
cout<<0;
return 0;
}
spfa(start,end);
cout<<dis[end];
return 0;
}
```
by EternalArthorn @ 2019-03-28 21:45:58
………………
by Leap_Frog @ 2019-03-28 22:09:52