最短路专题2 | CodeForces 449B - SPFA算法
最短路专题2 | CodeForces 449B - SPFA算法
最短路专题2 | CodeForces 449B - SPFA算法
B. Jzzhu and Cities
Jzzhu is the president of country A. There are n cities numbered from 1 to n in his country. City 1 is the capital of A. Also there are m roads connecting the cities. One can go from city to (and vise versa) using the -th road, the length of this road is . Finally, there are k train routes in the country. One can use the -th train route to go from capital of the country to city (and vise versa), the length of this route is . J是A国的总统，这个国家有n个城市。1是首都，有m条公路连接这些城市。然后，有k个火车线。城市到首都1的距离是。
Jzzhu doesn't want to waste the money of the country, so he is going to close some of the train routes. Please tell Jzzhu the maximum number of the train routes which can be closed under the following condition: the length of the shortest path from every city to the capital mustn't change. J不想浪费钱，删除部分铁路，但是每个城市到达首都的最短路径不能被修改，也就是说，只有最短路径不经过这个铁路时，才可以删除。
Input
The first line contains three integers .
Each of the next lines contains three integers .
Each of the next lines contains two integers and .
It is guaranteed that there is at least one way from every city to the capital. Note, that there can be multiple roads between two cities. Also, there can be multiple routes going to the same city from the capital. 保证至少有一条路从每个城市到达首都。注意，2个城市之间可能有多条路线。
Output
Output a single integer representing the maximum number of the train routes which can be closed. 火车线被关闭的数量
Examples
input
5 5 3
1 2 1
2 3 2
1 3 3
3 4 4
1 5 5
3 5
4 5
5 5
output
2
input
2 2 3
1 2 2
2 1 3
2 1
2 2
2 3
output
2
解题思路：
题意大概是说有多个城市，每个城市都和首都连接，有可能是公路，也有可能是铁路。为了削减开支，总统大人希望能够将现有的铁路拆掉，但是必须有一个前提，那就是拆了之后用户可以通过公路到达首都。而且路程不能比以前铁路的路程远。
这个题目看起来就是一道最短路径问题，不管是公路还是铁路，都将加入到图G中。然后求出每个城市到达首都的最短路径，在这个过程中，如果路径中存在铁路，就看下铁路能否用公路代替（看能否通过其他路线进行松弛处理），也就是说，在松弛的过程中，如果对象是铁路，则标记一下这个铁路可以被替换掉。
显然，这里提到了松弛操作，有同学就大概明白了会使用bellman-ford或者SPFA算法，因为BF算法就是通过不停的松弛处理来计算最短路径的。
本篇采用SPFA算法来处理这个问题。
SPFA算法性能通常要比BF好很多，不过最坏复杂度还是。
SPFA算法的全称是：Shortest Path Faster Algorithm。
注意：为了避免最坏情况的出现，在正权图上应使用效率更高的Dijkstra算法。
如果一个点进入队列达到n次，则表明图中存在负环，没有最短路径。
SPFA算法思路整理
SPFA算法是bellman-ford算法的改进版本，将之前的循环遍历改成了FIFO队列，然后通过优化的方式，提升性能。
一开始放入节点1到队列Q，然后开始循环，只要Q里面元素还存在，就不退出。每次都从Q里面取得一个元素u，循环遍历u的相邻节点v， 如果v的d可以更新，也就是松弛判定，那么就将v加入到队列中。
SPFA优化策略
SPFA算法有两个优化策略SLF和LLL——SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾；LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出队进行松弛操作。SLF 和 LLF 在随机数据上表现优秀，但是在正权图上最坏情况为 O(VE)，在负权图上最坏情况为达到指数级复杂度。
源代码 C++
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <deque>
#define LL long long
#define inf 0x3ffffffffffffffll
using namespace std;
int GetInt() {
int ret, ch;
while (!isdigit(ch = getchar()));
ret = ch - '0';
while (isdigit(ch = getchar()))
ret = (ret << 1) + (ret << 3) + ch - '0';
return ret;
}
LL GetLL() {
return (LL)GetInt();
}
const int maxn = 111111, maxm = 600666;
struct {
int to, nxt;
LL w;
} E[maxm];
int zh[maxn], tot = 0;
void AddEdge(int u, int v, LL w) {
E[++tot].to = v;
E[tot].nxt = zh[u];
E[tot].w = w;
zh[u] = tot;
}
LL d[maxn];
bool inq[maxn] = {};
bool T[maxn] = {};
deque<int> q;
int n, m, k;
void SPFA() {
while (!q.empty()) {
// 从第一个元素开始
int u = q.front();
q.pop_front();
//是否在队列中，防止重复进入队列
inq[u] = 0;
//遍历节点u的相邻的节点
for (int i = zh[u]; i; i = E[i].nxt) {
//相邻节点v
int v = E[i].to;
//查看是否需要松弛
LL D = d[u] + E[i].w;
if (D <= d[v] && T[v]){
// 如果是火车的城市松弛，标记火车为0
T[v] = 0;
}
//如果需要松弛
if (D < d[v]) {
//更新d值
d[v] = D;
//将相邻的节点加入到队列中，防止重复判断
if (!inq[v]) {
//标记已经在队列中
inq[v] = 1;
//优化，放在队列前面还是后面
if (d[v] <= d[q.size() ? q.front() : 0])
q.push_front(v);
else
q.push_back(v);
}
}
}
}
}
int main() {
while (!q.empty())
q.pop_front();
cin >> n >> m >> k;
// m个公路
for (int i = 1; i <= m; i++) {
int a, b;
LL c;
a = GetInt();
b = GetInt();
c = GetLL();
AddEdge(a, b, c);
AddEdge(b, a, c);
}
memset(d, 0x3f, sizeof(d));
d[1] = 0;
//插入位置1
q.push_back(1);
inq[1] = 1;
// k个铁路
for (int i = 1; i <= k; i++) {
// 输入a、b
int a = GetInt();
//距离b
LL b = GetLL();
d[a] = min(d[a], b);
// 如果a不在队列中，则将a放入队列
if (!inq[a]) {
q.push_back(a);
inq[a] = 1;
}
//标记城市a为有火车的
T[a] = 1;
}
// 开始spfa最短路算法
SPFA();
//当前还剩的火车数量
int nowC = 0;
for (int i = 1; i <= n; i++)
if (T[i])
nowC++;
//输出去掉的火车数量
cout << k - nowC << endl;
return 0;
}
如果用Dijkstra算法？
上面是SPFA算法实现的，但是如果想用Dijkstra算法呢？毕竟这里也没有负权的边，答案是肯定的，Dijkstra算法虽然不是松弛的做法，回顾上一篇，Dijkstra算法是分2个图，每次取一个最短d的边加入最短路中，本题使用Dijkstra可以先用Dijkstra算出最短路径，然后看下每一个城市到达首都的距离是不是变小了，如果变了，就说明这个首都到达这个城市的铁路可以拆掉。Dijkstra+优先队列的性能也是不输SPFA的，而且更加稳定。
点赞的时候，请宠溺一点