Spfa：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 const int maxn=100000+10,INF=-1u>>1; 8 struct Tedge{int x,y,w,next;}adj[maxn*2];int fch[maxn],ms=0; 9 void AddEdge(int u,int v,int w){ 10 adj[++ms]=(Tedge){u,v,w,fch[u]};fch[u]=ms;return; 11 } 12 bool vis[maxn];int dist[maxn],n,m; 13 void SPFA(){ 14 queue<int>Q;memset(vis,false,sizeof(vis)); 15 for(int i=1;i<=n+1;i++)dist[i]=INF;dist[1]=0; 16 Q.push(1);vis[1]=true; 17 while(!Q.empty()){ 18 int u=Q.front();Q.pop();vis[u]=false; 19 for(int i=fch[u];i;i=adj[i].next){ 20 int v=adj[i].y; 21 if(dist[v]>dist[u]+adj[i].w){ 22 dist[v]=dist[u]+adj[i].w; 23 if(!vis[v]) vis[v]=true,Q.push(v); 24 } 25 } 26 } return ; 27 } 28 inline int read(){ 29 int x=0,sig=1;char ch=getchar(); 30 while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();} 31 while(isdigit(ch)) x=10*x+ch-'0',ch=getchar(); 32 return x*=sig; 33 } 34 inline void write(int x){ 35 if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x; 36 int len=0,buf[15];while(x) buf[len++]=x%10,x/=10; 37 for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return; 38 } 39 void init(){ 40 n=read();m=read();int a,b,c; 41 for(int i=1;i<=m;i++){ 42 a=read();b=read();c=read(); 43 AddEdge(a,b,c);//printf("-AddEdge-%d %d %d ",k,j,c); 44 } return; 45 } 46 void work(){ 47 SPFA(); 48 //for(int i=1;i<=ms;i++)printf("-Edge- %d to %d is %d ",adj[i].x,adj[i].y,adj[i].w); 49 //for(int i=1;i<=n+1;i++) printf("dist[%d]=%d ",i,dist[i]); 50 return; 51 } 52 void print(){ 53 if(dist[n+1]>=INF) puts("No Answer."); 54 else write(dist[n+1]),putchar(' '); 55 return; 56 } 57 int main(){ 58 init();work();print();return 0; 59 }