题目描述

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

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

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

样例

输入样例：
3 3
1 2 5
2 3 -3
1 3 4
输出样例：
2

算法1

(spfa模板) $O(KE)$

直接套spfa模板

时间复杂度 $O(KE)$

参考文献 无

C++ 代码

#include<bits/stdc++.h>
const int N=1e5+1000,M=2e5+1000,INF=0x3f3f3f3f;
int n,m,tot,x,y,z,first[N],ne[M],to[M],w[M],dis[N];
bool exist[N];
std::queue<int>q;
void add(int x,int y,int z){
    ne[++tot]=first[x];
    first[x]=tot;
    to[tot]=y;
    w[tot]=z;
}
void input(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n>>m;
    for(int i=0;i<m;i++){
        std::cin>>x>>y>>z;
        add(x,y,z);
    }
}
int main(){
    input();
    memset(dis,INF,sizeof(dis));
    dis[1]=0;
    q.push(1);
    exist[1]=true;
    while(!q.empty()){
        int u=q.front();
        int e=first[u];
        exist[u]=false;
        q.pop();
        while(e){
            int v=to[e];
            if(dis[u]+w[e]<dis[v]){
                dis[v]=dis[u]+w[e];
                if(exist[v]==false){
                    q.push(v);
                    exist[v]=true;
                }
            }
            e=ne[e];
        }
    }
    if(dis[n]!=INF)std::cout<<dis[n]<<std::endl;
    else std::cout<<"impossible"<<std::endl;
    return 0;
}