本文共 1385 字，大约阅读时间需要 4 分钟。

给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出impossible。

数据保证不存在负权回路。

输入格式

接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

输出格式

如果路径不存在，则输出”impossible”。

数据范围

输入样例：

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const   int N=200010;int h[N],e[N],ne[N],idx;int w[N];bool st[N];int d[N];void add(int a,int b,int c){       e[idx]=b;    w[idx]=c;    ne[idx]=h[a];    h[a]=idx++;    }int m,n,k;int spfa(){       queue
       
        q;    memset(d,0x3f,sizeof(d));    d[1]=0;    st[1]=1;    q.push(1);    while(q.size())    {           int t=q.front();        q.pop();        st[t]=0;        for(int i=h[t];i!=-1;i=ne[i])        {               int j=e[i];            if(d[j]>d[t]+w[i])            {                   d[j]=d[t]+w[i];                if(!st[j])                {                       st[j]=1;                    q.push(j);                }            }        }    }    if(d[n]>0x3f3f3f3f/2)   return 0;    else    return d[n];}int main(){       memset(h,-1,sizeof(h));    cin>>n>>m;    while(m--)    {           int a,b,c;        cin>>a>>b>>c;        add(a,b,c);    }    if(spfa()){           printf("%d\n",spfa());    }    else        {               printf("impossible\n");        }        return 0;}