Easy SSSP

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 2510 字
虚拟源点判负环再跑一次SPFA
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1508
// 题意：给 n 点 m 边有向图和源点 s，若全图存在负环只输出 -1，否则逐点输出 s 到该点的最短路，不可达输出 NoPath。
// 思路：先加虚拟源点 0 连向所有点做一次 SPFA 判全图负环，再从 s 单独跑一次 SPFA 求最短路。
// 1. 负环判定必须在全图上做，只从 s 出发会漏掉 s 到不了的负环。
// 2. 第二次 SPFA 只需从 s 出发，dis[s] 置 0 其余置无穷。
// 复杂度：O(k * m) 时间 / O(n + m) 空间
// 易错点：边权绝对值可达 1e6 且点数 1e3，最短路要用 long long，用 int 会溢出。
// 易错点：负环判定用入队次数超过 n + 1，松弛时不要忘记把节点重新入队。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const long long INF = (1LL << 60);
struct Edge{
    int to;
    long long w;
};
vector<Edge> g[MAXN];
long long dis[MAXN];
int cnt[MAXN];
bool inq[MAXN];
int main(){
    int n, m, s;
    if(!(cin >> n >> m >> s)) return 0;
    for(int i = 0; i < m; i++){
        int a, b;
        long long c;
        cin >> a >> b >> c;
        Edge e;
        e.to = b;
        e.w = c;
        g[a].push_back(e);
    }
    for(int i = 1; i <= n; i++){
        Edge e;
        e.to = i;
        e.w = 0;
        g[0].push_back(e);
    }
    queue<int> q;
    for(int i = 0; i <= n; i++){
        dis[i] = 0;
        cnt[i] = 0;
        inq[i] = true;
        q.push(i);
    }
    bool neg = false;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        inq[u] = false;
        for(int i = 0; i < (int)g[u].size(); i++){
            int v = g[u][i].to;
            long long w = g[u][i].w;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                cnt[v]++;
                if(cnt[v] > n + 1){
                    neg = true;
                    break;
                }
                if(!inq[v]){
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
        if(neg) break;
    }
    if(neg){
        cout << -1 << "\n";
        return 0;
    }
    for(int i = 1; i <= n; i++){
        dis[i] = INF;
        cnt[i] = 0;
        inq[i] = false;
    }
    dis[s] = 0;
    inq[s] = true;
    q.push(s);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        inq[u] = false;
        for(int i = 0; i < (int)g[u].size(); i++){
            int v = g[u][i].to;
            long long w = g[u][i].w;
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                if(!inq[v]){
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(dis[i] >= INF / 2) cout << "NoPath" << "\n";
        else cout << dis[i] << "\n";
    }
    return 0;
}
Easy SSSP

正文

一本通·提高篇的其它内容
