12月27日星期六9:00-12:00

SPFA求最短路径

S+03L04有负权边的最短路

描述

给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。

输入描述

第一行两个整数n, m。

接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。

对于10%的数据，n = 2，m = 2。

对于30%的数据，n <= 5，m <= 10。

对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

输出描述

共n-1行，第i行表示1号点到i+1号点的最短路。

用例输入 1

用例输出 1

-1
-2

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, k, pre[21000];  // 记录以i起点的最后一条边在数组a的下标
int d[21000];             // 到i点的最短距离
int f[21000];             // 记录i点是否在数组里面
queue<int> q;
struct Edge {
    int from, to, len, next;  // 边的起点 终点 权值 上一条边在数组a的下标
} a[210000];
void add(int u, int v, int len) {
    a[++k].from = u;
    a[k].to = v;
    a[k].len = len;
    a[k].next = pre[u];
    pre[u] = k;
}
int main() {
    cin >> n >> m;
    for (int i = 0; i <  m; i++) {
        int u, v, len;
        cin >> u >> v >> len;
        add(u, v, len);
    }
    memset(d, 0x3f, sizeof(d));
    d[1] = 0;
    q.push(1);
    f[1] = true;
    while (!q.empty()) {
        int h = q.front();
        // h点有没有短路路
        for (int i = pre[h]; i != 0; i = a[i].next) {
            int to = a[i].to;  // 要到的点
            if (a[i].len + d[h] < d[to]) {
                d[to] = d[h] + a[i].len;
                if (!f[to]) {
                    q.push(to);
                    f[to] = true;
                }
            }
        }
        q.pop();
        f[h] = false;
    }
    for (int i = 2; i <= n; i++) {
        cout << d[i] << endl;
    }
    return 0;
}

P3385 【模板】负环

题目描述

给定一个 n 个点的有向图，请求出图中是否存在从顶点 1 出发能到达的负环。

负环的定义是：一条边权之和为负数的回路。

输入格式

本题单测试点有多组测试数据。

输入的第一行是一个整数 T，表示测试数据的组数。对于每组数据的格式如下：

第一行有两个整数，分别表示图的点数 n 和接下来给出边信息的条数 m。

接下来 m 行，每行三个整数 u, v, w。

若 w \geq 0，则表示存在一条从 u 至 v 边权为 w 的边，还存在一条从 v 至 u 边权为 w 的边。
若 w < 0，则只表示存在一条从 u 至 v 边权为 w 的边。

输出格式

对于每组数据，输出一行一个字符串，若所求负环存在，则输出 YES，否则输出 NO。

输入输出样例 #1

输入 #1

输出 #1

NO
YES

说明/提示

数据规模与约定

对于全部的测试点，保证：

1 \leq n \leq 2 \times 10^3，1 \leq m \leq 3 \times 10^3。
1 \leq u, v \leq n，-10^4 \leq w \leq 10^4。
1 \leq T \leq 10。

提示

请注意，m 不是图的边数。

代码

/**
 * 易错点:
 * 1.m不一定等于图的边,需要考虑无向图
 * 2.数据初始化问题 如f cnt pre k
 */
#include <bits/stdc++.h>
using namespace std;
int t, n, m, k;
int pre[2100];  // 存以i为起点 在数组a的最后一条边
struct Edge {
    int from, to, next, len;
} a[6100];
void add(int u, int v, int len) {
    a[++k].from = u;
    a[k].to = v;
    a[k].len = len;
    a[k].next = pre[u];
    pre[u] = k;
}
int d[2100];
bool f[2100];
int cnt[2100];  // i结点 入队的次数
bool spfa(queue<int> q) {
    while (!q.empty()) {
        int head = q.front();  // 获得头结点的值
        q.pop();
        f[head] = false;
        // i就是以head为起点 在a数组的下标是多少
        for (int i = pre[head]; i != 0; i = a[i].next) {
            int to = a[i].to;  // head这个点可以到的结点编号
            if (d[to] > d[head] + a[i].len) {
                d[to] = d[head] + a[i].len;
                if (!f[to]) {
                    q.push(to);
                    f[to] = true;
                    cnt[to]++;
                    // 如果入队次数>=n说明有负环
                    if (cnt[to] >= n) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}
int main() {
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
            int u, v, len;
            cin >> u >> v >> len;
            if (len >= 0) {
                add(u, v, len);
                add(v, u, len);
            } else {
                add(u, v, len);
            }
        }
        // 用SFPA求最短路 如果有一个点 入队>=n次 说明存在有环
        memset(d, 0x3f, sizeof(d));
        d[1] = 0;
        queue<int> q;
        q.push(1);
        f[1] = true;
        if (spfa(q)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
        memset(f, 0, sizeof(f));
        memset(cnt, 0, sizeof(cnt));
        memset(pre, 0, sizeof(pre));
        k = 0;
    }
    return 0;
}