题目描述
带负权边的最短路,如果有负环输出 −1
否则输出 s 到每个点的最短距离,如果不能抵达输出NoPath
输入样例
6 8 1
1 3 4
1 2 6
3 4 -7
6 4 2
2 4 5
3 6 3
4 5 1
3 5 4
输出样例
0
6
4
-3
-2
7
算法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;
}
救命,大佬看看我的为啥最后一个案例过不去
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]);
}
}
}
博主,请问最后一个样例为什么过不了啊,求救:
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; } } }
你这个是WA2,35行改成
count[to] = count[v] + 1;
是TLE最后一个点看你判断负环的时候跑了n次spfa,可以考虑先所有点入队跑1次spfa判负环
博主,请问为什么要以所有点作为起点跑一边呢?判负环一个点跑不行吗
平时判负环都是 跑起点的,现在有点懵!!!
一个点一个点跑也行啊,但是你跑n次这复杂度不就高了吗
我的意思是,不是只跑一个点就可以判有没有负环了吗
并不行,图不一定是联通的,可能图中有负环但从起点不能抵达
膜拜一下hh