AcWing 1168. 简单单源最短路径问题【spfa】

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1168. 简单单源最短路径问题【spfa】原题链接简单

作者：

滑稽_ωﾉ , 2020-04-06 15:00:34 , 所有人可见 , 阅读 2044

7

1

题目描述

带负权边的最短路，如果有负环输出 $-1$
否则输出 $s$ 到每个点的最短距离，如果不能抵达输出NoPath

输入样例

输出样例

算法1 $spfa$

时间复杂度 $O(能过)$

先把所有点作为起点判一手负环，定义$len[i]$ 为任意点抵达 $i$ 的最短路径所包含的点数，如果 $len[i] > n$ 则说明最短路径中有超过 $n$ 个点，则存在负环。

然后再把 $s$ 作为起点重新求一下最短路

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 1010, M = 1e5 + 10, INF = 0x3f3f3f3f;

int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int n, m, s;
int d[N], len[N];

int q[N];
bool st[N];

bool spfa(vector<int> &roots)
{
    memset(d, 0x3f, sizeof d);

    int hh = 0, tt = 0;
    for(int i : roots)
    {
        q[tt ++] = i;
        st[i] = true;
        d[i] = 0;
        len[i] = 1;
    }

    while(hh != tt)
    {
        int u = q[hh ++];
        st[u] = false;

        if(hh == N)  hh = 0;
        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i], dist = d[u] + w[i];
            if(dist < d[j])
            {
                d[j] = dist;
                len[j] = len[u] + 1;
                if(len[j] > n)  return false;

                if(!st[j])
                {
                    q[tt ++] = j;
                    st[j] = true;
                    if(tt == N)  tt = 0;
                }
            }
        }
    }
    return true;
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d%d", &n, &m, &s);
    while(m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    vector<int> roots;
    for(int i = 1; i <= n; i ++)  roots.push_back(i);
    if(!spfa(roots))
    {
        puts("-1");
        return 0;
    }

    vector<int> start;
    start.push_back(s);
    spfa(start);

    for(int i = 1; i <= n; i ++)
        if(d[i] == INF)  puts("NoPath");
        else  printf("%d\n", d[i]);
    return 0;
}

方法 2

入队次数 >= n 时有负环

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;

const int N = 1010, M = 100010;
const LL INF = 0x3f3f3f3f3f3f3f3f;

int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

LL d[N];
int n, m, S;
int q[N], cnt[N];
bool st[N];
bool spfa(vector<int> &v)
{
    memset(cnt, 0, sizeof cnt);
    memset(d, 0x3f, sizeof d);
    memset(st, 0, sizeof st);

    int hh = 0, tt = 0;
    for(int j : v)
    {
        d[j] = 0;
        cnt[j] ++;
        q[tt ++] = j;
        st[j] = true;
    }

    while(hh != tt)
    {
        int u = q[hh ++];  if(hh == N)  hh = 0;
        st[u] = false;

        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            LL dist = d[u] + w[i];
            if(dist < d[j])
            {
                d[j] = dist;
                if(!st[j])
                {
                    if( ++ cnt[j] == n)  return true;
                    q[tt ++] = j;  if(tt == N)  tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d%d", &n, &m, &S);
    while(m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    vector<int> v;
    for(int i = 1; i <= n; i ++)  v.push_back(i);

    if(spfa(v))  return 0 * puts("-1");

    v.clear();
    v.push_back(S);

    spfa(v);
    for(int i = 1; i <= n; i ++)
        if(d[i] == INF)  puts("NoPath");
        else  printf("%lld\n", d[i]);
    return 0;
}

9 评论

小皓 7个月前

救命，大佬看看我的为啥最后一个案例过不去
import java.util.*;

public class E22 {
static int N=1005;
static int n,idx;
static int[]e=new int[N];
static int[]ne=new int[N];
static int[]h=new int[N];
static int[]w=new int[N];
static int[]dist=new int[N];
static int[]cnt=new int[N];
static boolean[]st=new boolean[N];
static void spfa(int s){
Arrays.fill(dist,Integer.MAX_VALUE);
dist[s]=0;
Queue[HTML_REMOVED]queue=new LinkedList<>();
queue.offer(s);
st[s]=true;
while (!queue.isEmpty()){
Integer polled = queue.poll();
st[polled]=false;
for(int i=h[polled];i!=-1;i=ne[i]){
int j = e[i];
if(dist[j]>dist[polled]+w[i]){
dist[j]=dist[polled]+w[i];
if(!st[j]){
queue.offer(j);
st[j]=true;
}
}
}
}
}
static boolean spfa(){
Queue[HTML_REMOVED]queue=new LinkedList<>();
for (int i = 1; i <= n; i) {
queue.offer(i);
st[i]=true;
}
while (!queue.isEmpty()){
Integer polled = queue.poll();
st[polled]=false;
for (int i=h[polled];i!=-1;i=ne[i]){
int j = e[i];
if(dist[j]>dist[polled]+w[i]){
dist[j]=dist[polled]+w[i];
cnt[j]=cnt[polled]+1;
if(cnt[j]>=n) return true;
if(!st[j]){
queue.offer(j);
st[j]=true;
}
}
}
}
return false;
}
static void add(int a,int b,int c){
e[idx]=b;
ne[idx]=h[a];
w[idx]=c;
h[a]=idx;
}
public static void main(String[] args) {
Arrays.fill(h,-1);
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
int m = sc.nextInt();
int s = sc.nextInt();
for (int i = 0; i < m; i) {
int a = sc.nextInt();
int b = sc.nextInt();
int w = sc.nextInt();
add(a,b,w);
}
if(spfa()) System.out.println(-1);
spfa(s);
for (int i = 1; i <= n; i) {
if(dist[i]==Integer.MAX_VALUE) System.out.println(“NoPath”);
else System.out.println(dist[i]);
}
}
}

yxc胡建分灿 2020-04-14 09:07

博主，请问最后一个样例为什么过不了啊，求救：

import java.util.*;
import java.math.*;
import java.io.*;
public class Main{
    static int V, E;
    static int INF = 0x3f3f3f3f;
    static int MAXN = (int)1e5 + 50;
    static Edge[] edges;
    static int[] dist, count, head;
    static int tot;
    static boolean[] inq;
    static void addEdge(int u, int v, int w) {
        edges[++tot] = new Edge();
        edges[tot].to = v;
        edges[tot].w = w;
        edges[tot].next = head[u];
        head[u] = tot;
    }
    static boolean spfa(int S) {
        inq = new boolean[MAXN];
        count = new int[MAXN];
        dist = new int[MAXN];
        Arrays.fill(dist, INF);
        dist[S] = 0;
        Queue<Integer> q = new ArrayDeque<>();
        q.add(S);
        inq[S] = true;

        while (!q.isEmpty()) {
            int v = q.poll();
            inq[v] = false;
            for (int i = head[v]; i != 0; i = edges[i].next) {
                int to = edges[i].to, w  = edges[i].w;
                if (dist[to] > dist[v] + edges[i].w) {
                    count[to] = count[i] + 1;
                    if (count[to] > V)
                        return true;
                    dist[to] = dist[v] + edges[i].w;
                    if (!inq[to]) {
                        q.add(to);
                        inq[to] = true;
                    }
                }
            }
        }
        return false;
    }
    public static void main(String[] args) throws IOException {  
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));

        V = sc.nextInt();
        E = sc.nextInt();
        int S = sc.nextInt();
        inq = new boolean[MAXN];
        count = new int[MAXN];
        dist = new int[MAXN];
        edges = new Edge[MAXN];
        head = new int[MAXN];

        for (int i = 1; i <= E; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            addEdge(a, b, c);
        }
        for (int i = 1; i <= V; i++) {
            if (spfa(i))  {
                System.out.println(-1);
                return;
            }
        }
        boolean res = spfa(S);
        if (res)  {System.out.println(-1);return;}
        for (int i = 1; i <= V; i++) {
            if (dist[i] == INF)
                System.out.println("NoPath");
            else 
                System.out.println(dist[i]);
        }
    }
    static class Edge {
        int to, w, next;
        Edge() {}
        Edge(int to, int w, int next) {
            this.to = to;
            this.w = w;
            this.next = next;
        }
    } 
}