2018-11-17 19:28:28

### Output

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#define R register

using namespace std;

const int gz=5e4+8;

inline void in(R int &x)
{
R int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}

struct cod{int u,v,w;}edge[gz<<1],e[gz<<1];

inline void add(R int x,R int y,R int z)
{
edge[tot].v=y;
edge[tot].w=z;
}

inline void ado(R int x,R int y)
{
e[++cnt].u=pr[x];
e[cnt].v=y;
pr[x]=cnt;
}

int dis[gz],real[gz],n,m;

bool vis[gz];

struct hop
{
int u,d;
bool operator <(const hop&a)const
{
return d>a.d;
};
};

inline void dij()
{
for(R int i=1;i<=n;i++)dis[i]=2147483644;
priority_queue<hop>q;dis[1]=real[1]=0;
q.push((hop){1,0});
while(!q.empty())
{
R int u=q.top().u;q.pop();
if(vis[u])continue;
vis[u]=true;
R int now=max(dis[u],real[u]);
{
if(dis[edge[i].v]>now+edge[i].w)
{
dis[edge[i].v]=now+edge[i].w;
if(hd[edge[i].v]==0)
q.push((hop){edge[i].v,max(dis[edge[i].v],real[edge[i].v])});
}
}
for(R int i=pr[u];i;i=e[i].u)
{
hd[e[i].v]--;
real[e[i].v]=max(real[e[i].v],now);
if(hd[e[i].v]==0)
q.push((hop){e[i].v,max(real[e[i].v],dis[e[i].v])});
}
}
printf("%d\n",max(real[n],dis[n]));
}

int main()
{
in(n),in(m);
for(R int i=1,x,y,z;i<=m;i++)
{
in(x),in(y),in(z);
if(x==y)continue;
}