最短路专题3| CF 20C - SPFA带环图
最短路专题3| CF 20C - SPFA带环图
C. Dijkstra?
You are given a weighted undirected graph. The vertices are enumerated from 1 to n. Your task is to find the shortest path between the vertex 1 and the vertex n.
给定一个带权重的无向图，节点从1到n。找出节点1和节点n的最短路径。
Input
The first line contains two integers n and m (), where n is the number of vertices and m is the number of edges. Following m lines contain one edge each in form , and (), where , are edge endpoints and is the length of the edge.
第一行包含2个整数n和m，n是节点数量，m是边数。接下来m条边表示节点到节点以及权重。
It is possible that the graph has loops and multiple edges between pair of vertices. 图G可能有环。
Output
Write the only integer -1 in case of no path. Write the shortest path in opposite case. If there are many solutions, print any of them.
如果没有最短路，输出-1，反之输出最短路径，如果存在多种情况，输出其中一条即可。
Examples
input
5 6 1 2 2 2 5 5 2 3 4 1 4 1 4 3 3 3 5 1
output
1 4 3 5
input
5 6 1 2 2 2 5 5 2 3 4 1 4 1 4 3 3 3 5 1
output
1 4 3 5
解题思路：
本题和上一篇其实比较相似，采用了SPFA算法，注意图G是双向的。
代码如下：C++
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
vector<vector<pair<int, long long>>> graph;
vector<long long> dist;
vector<int> parent, ans;
vector<bool> visited;
deque<int> q;
int n, m, a, b, c;
#define pc(x) putchar(x)
#define gc() getchar()
inline void writeInt(int n) {
int N = n, rev, count = 0;
rev = N;
if (N == 0) {
pc('0');
pc('\n');
return;
}
while ((rev % 10) == 0) {
count++;
rev /= 10;
}
rev = 0;
while (N != 0) {
rev = (rev << 3) + (rev << 1) + N % 10;
N /= 10;
}
while (rev != 0) {
pc(rev % 10 + '0');
rev /= 10;
}
while (count--)
pc('0');
pc(' ');
}
inline int FAST_IO() {
char ch;
int val = 0;
ch = gc();
while (ch == '\n' || ch == ' ')
ch = gc();
val = 0;
while (ch >= '0' && ch <= '9') {
val = (val * 10) + (ch - '0');
ch = gc();
}
return val;
}
int main() {
// 输入n和m
n = FAST_IO();
m = FAST_IO();
//
graph.resize(n + 5);
while (m--) {
a = FAST_IO();
b = FAST_IO();
c = FAST_IO();
// 双向输入边
graph[a].push_back(make_pair(b, c));
graph[b].push_back(make_pair(a, c));
}
dist.resize(n + 5, 1e16);
parent.resize(n + 5, -1);
visited.resize(n + 5);
// 从节点1开始
dist[1] = 0;
q.push_back(1);
while (!q.empty()) {
// 取出节点
int v = q.front();
visited[v] = true;
q.pop_front();
// 遍历相邻的边
for (size_t i = 0; i < graph[v].size(); ++i) {
int to = graph[v][i].first;
int len = graph[v][i].second;
// 更新d值
if (dist[to] > dist[v] + len) {
dist[to] = dist[v] + len;
// 记录路径
parent[to] = v;
//spfa算法，如果没有访问过，就放到前面，优先遍历
if (!visited[to])
q.push_front(to);
else
q.push_back(to);
visited[to] = true;
}
}
}
if (dist[n] < 1e16) {
for (int i = n; i != -1; i = parent[i])
ans.push_back(i);
for (int i = ans.size() - 1; i > -1; --i)
writeInt(ans[i]);
} else
printf("-1");
return 0;
}
简单看完SPFA算法，可以再来了解一下Dijsktra算法对于负权的问题。
Dijsktra算法处理负权?
我们看看下面这张图：
负权图
算法刚开始执行时，将1添加到集合中标记已访问，之后选出从1到所有节点中的最短的d，于是把3加入集合中标记已访问，之后3不能在更新了，而显然，1与3之间最短路径权值为1（1-2-3），发生错误。
好啦，大概讲这些，可以思考一下：Dijkstra算法如何处理负权？