当前位置：首页 > news >正文

信息学奥赛一本通 1508：Easy SSSP

news 来源：原创 2025/8/25 12:19:55

【题目链接】

ybt 1508：Easy SSSP

【题目考点】

1. SPFA算法判断负环

【解题思路】

使用SPFA统计整个图中是否有负环，初始需要将所有顶点都入队。
可以假想存在一个超级源点，第0号顶点。第0号顶点到第1到第n号顶点都有权值为0的边。
（或者可以分别以第1号到第n号顶点为源点，运行SPFA算法，判断是否存在负权环。判断是否存在负权环可以使用DFS版本的SPFA，相对效率更高。）
执行SPFA算法时，统计顶点的入队次数，如果入队次数大于n，则存在负权环。
而后再以S为源点求单源最短路径。

【题解代码】

解法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';elsecout << 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;elsecout << dis[i] << endl;}return 0;
}