信息学奥赛一本通 1508：Easy SSSP-题解代码

解法1：SPFA算法找负环和求最短路径 设超级源点

#include<bits/stdc++.h>
using namespace std;
#define N 1005
#define INF 0x3f3f3f3f3f3f3f3f
struct Edge
{
	int v, w;
};
long long n, m, s, dis[N], enqueNum[N];
vector<Edge> edge[N];
bool inQue[N];
bool spfa(int sv)//返回是否有负环 
{
	memset(dis, 0x3f, sizeof(dis));
	queue<int> que;
	dis[sv] = 0;
	que.push(sv);
	inQue[sv] = true;
	enqueNum[sv]++;
	while(!que.empty())
	{
		int u = que.front();
		que.pop();
		inQue[u] = false;
		for(Edge e : edge[u])
		{
			int v = e.v, w = e.w;
			if(dis[v] > dis[u]+w)
			{
				dis[v] = dis[u]+w;
				if(!inQue[v])
				{
					if(++enqueNum[v] > n)
						return true;		
					que.push(v);
					inQue[v] = true;
				}
			}
		}
	}
	return false;
}
int main()
{
	int u, v, w;
	cin >> n >> m >> s;
	for(int i = 1; i <= m; ++i)
	{
		cin >> u >> v >> w;
		edge[u].push_back(Edge{v, w});
	}
	for(int i = 1; i <= n; ++i)//添加超级源点
		edge[0].push_back(Edge{i, 0}); 
	bool hasNegRing = spfa(0);
	if(hasNegRing)
		cout << -1;
	else
	{
		spfa(s);
		for(int i = 1; i <= n; ++i)
		{
			if(dis[i] == INF)
				cout << "NoPath" << '\n';
			else
				cout << dis[i] << '\n';
		}
	}
	return 0;
}

解法2：尝试从每个顶点出发调用SPFA_DFS算法找负环，SPFA求最短路径

#include <bits/stdc++.h>
using namespace std;
#define N 1005
#define INF 0x3f3f3f3f3f3f3f3f
struct Edge
{
	int v, w;
};
int n, m, s;
long long dis[N];
vector<Edge> edge[N];
bool inStk[N], inQue[N], hasNegRing;
void spfa_dfs(int u)
{
	if(hasNegRing)
		return;
	inStk[u] = true;
	for(Edge e : edge[u])
	{
		int v = e.v, w = e.w;
		if(dis[v] > dis[u]+w)
		{
			dis[v] = dis[u]+w;
			if(inStk[v])//找到负环 
			{
				hasNegRing = true;
				return;
			}
			spfa_dfs(v);
		}
	}
	inStk[u] = false;
}
void spfa_bfs(int u)
{
	memset(dis, 0x3f, sizeof(dis));
	queue<int> que;
	inQue[u] = true;
	dis[u] = 0;
	que.push(u);
	while(!que.empty())
	{
		int u = que.front();
		que.pop();
		inQue[u] = false;
		for(Edge e : edge[u])
		{
			int v = e.v, w = e.w;
			if(dis[v] > dis[u]+w)
			{
				dis[v] = dis[u]+w;
				if(!inQue[v]) 
				{
					inQue[v] = true;
					que.push(v);
				}
			}
		}	
	}
}
int main()
{
	int f, t, w;
	cin >> n >> m >> s;
	for(int i = 1; i <= m; ++i)
	{
		cin >> f >> t >> w;
		edge[f].push_back(Edge{t, w});
	}
	for(int v = 1; v <= n; ++v)
	{
		spfa_dfs(v);
		if(hasNegRing)
		{
			cout << -1;
			return 0;
		}
	}
	spfa_bfs(s);
	for(int i = 1; i <= n; ++i)
	{
		if(dis[i] == INF)
			cout << "NoPath" << endl;
		else
			cout << dis[i] << endl;
	}
	return 0;
}