给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示点x和点y之间存在一条有向边，边长为z。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出”impossible”。
数据范围
1≤n,m≤1051≤n,m≤105, 图中涉及边长绝对值均不超过10000。
输入样例：
3 3 1 2 5 2 3 -3 1 3 4输出样例：
2#include<bits/stdc++.h> using namespace std; const int N=1e5+100; int e[N],ne[N],w[N],h[N],idx; int dist[N]; bool st[N]; int n,m; void add(int a,int b,int c) { e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++; } int spfa() { memset(dist,0x3f3f3f3f,sizeof dist); dist[1]=0; queue<int>q; q.push(1); st[1]=true; // while(q.size()) { int t=q.front(); q.pop(); st[t]=false; // for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+w[i]) { dist[j]=dist[t]+w[i]; if(!st[j]) { q.push(j); st[j]=true; } } } } if(dist[n]==0x3f3f3f3f) { return -1; } return dist[n]; } int main() { cin>>n>>m; memset(h,-1,sizeof h); while(m--) { int a,b,c; cin>>a>>b>>c; add(a,b,c); } int t= spfa(); if(t==-1) { cout<<"impossible"; } else{ cout<<t; } return 0; }
