本题我在使用spfa求势能h时需要对h赋初始值才能使答案正确

但如果使用Bellman-Ford则不需要给h赋初值

难道不是只关心势能的差值吗？

为什么spfa时对h的初值会有一定要求？

#include <bits/stdc++.h>
using namespace std;

//#define int long long

inline int read()
{
	int a = 0, b = 1; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') b = -1; c = getchar(); }
	while(c <= '9' && c >= '0') { a = a * 10 + c - 48; c = getchar(); }
	return a * b;
}

inline void write(int n)
{
    if(n > 9) write(n / 10);
    putchar(n % 10 + 48);
}

#define pii pair<int, int>

const int N = 3e3 + 20;

int n, m, u, v, w;
int h[N], dis[N], vis[N], flag[N];
int flagd[N];
vector<pii> e[N];

void spfa()
{
	memset(h, 10, sizeof(h)); h[0] = 0;
   //不加上面这一行就会出错
	for(int i = 1 ; i <= n ; ++ i) e[0].push_back(make_pair(0, i));
	queue<int> q1;
	q1.push(0);
	while(!q1.empty())
	{
		int t = q1.front(); q1.pop(); flag[t] = 0;
		for(auto _ : e[t])
		{
			int d = h[t] + _.first;
			if(d < h[_.second])
			{
				h[_.second] = d; vis[_.second] = vis[t] + 1;
				if(vis[_.second] == n + 1)
				{
					printf("-1\n");
					exit(0);
				}
				if(flag[_.second] == 0)
				{
//					vis[_.second] ++;
//					if(vis[_.second] == n + 1)
//					{
//						printf("-1\n");
//						exit(0);
//					}
					q1.push(_.second);
					flag[_.second] = 1;
				}
			}
		}
	}
	return;
}

void dj(int s)
{
	priority_queue<pii, vector<pii>, greater<pii> > q2;
	memset(flagd, 0, sizeof(flagd)); memset(dis, 0x3f, sizeof(dis)); dis[s] = 0;
	q2.push(make_pair(0, s));
	while(!q2.empty())
	{
		auto t = q2.top(); q2.pop();
		if(flagd[t.second]) continue;
		else flagd[t.second] = 1;
		for(auto _ : e[t.second])
		{
			int d = dis[t.second] + _.first + h[t.second] - h[_.second], id = _.second;
			if(d < dis[id])
			{
				dis[id] = d;
				q2.push(make_pair(d, id));
			}
		}
	} 
	return;
}

void bf()
{
	for(int i = 1 ; i <= n ; ++ i)
	{
		bool found = 0;
		for(int j = 1 ; j <= n ; ++ j)
		{
			for(auto _ : e[j])
			{
				if(h[j] + _.first < h[_.second])
				{
					found = 1;
					h[_.second] = h[j] + _.first;
				}
			}
		}
		if(found && i == n)
		{
			printf("-1\n");
			exit(0);
		}
	}
}

int main()
{
	//ios::sync_with_stdio(false);
	n = read(); m = read();
	for(int i = 1 ; i <= m ; ++ i)
	{
		u = read(); v = read(); w = read();
		e[u].push_back(make_pair(w, v));
	}
	spfa();
	//bf();
	for(int i = 1 ; i <= n ; ++ i)
	{
		long long ans = 0;
		dj(i);
		for(int j = 1 ; j <= n ; ++ j)
		{
			if(dis[j] == dis[0]) ans += 1ll * j * 1e9;
			else if(i == j) continue;
			else ans += 1ll * j * (dis[j] - h[i] + h[j]);
		}
		printf("%lld\n", ans);
	}
	return 0;
}
//start coding at  :
//finish debugging at  :