蓝桥杯-算法训练--ALGO-5 最短路

时间:2021-12-01 12:10:04
问题描述

给定一个n个顶点,m条边的有向图(其中某些边权可能为负,但保证没有负环)。请你计算从1号点到其他点的最短路(顶点从1到n编号)。

输入格式

第一行两个整数n, m。

接下来的m行,每行有三个整数u, v, l,表示u到v有一条长度为l的边。

输出格式
共n-1行,第i行表示1号点到i+1号点的最短路。
样例输入
3 3
1 2 -1
2 3 -1
3 1 2
样例输出
-1
-2
数据规模与约定

对于10%的数据,n = 2,m = 2。

对于30%的数据,n <= 5,m <= 10。

对于100%的数据,1 <= n <= 20000,1 <= m <= 200000,-10000 <= l <= 10000,保证从任意顶点都能到达其他所有顶点。

 
 
一开始的时候规模少看了一个零( =  = !!)  
用了写起来比较简单的floyd算法自己变形了一下,以下错误代码:
#include<cstdio>
#include
<iostream>
#include
<cstring>
using namespace std;
const int MAXN = 20001;
int floyd[MAXN][MAXN];
int main(){
int m, n;
memset(floyd,
2, sizeof(floyd));
cin
>> m >> n;
for (int i = 1; i <= m; i++){
int from, to, value;
cin
>> from >> to >> value;
floyd[
from][to] = value;
}
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++){
if (floyd[1][k] + floyd[k][j] < floyd[1][j])
floyd[
1][j] = floyd[1][k] + floyd[k][j];
}
for (int m = 2; m <= n; m++)
cout
<< floyd[1][m] << endl;
return 0;
}

 

上网查了一下发现SPFA算法,利用队列优化了一下。

SPFA(Shortest Path Faster Algorithm)(队列优化)算法是求单源最短路径的一种算法,它还有一个重要的功能是判负环(在差分约束系统中会得以体现),在Bellman-ford算法的基础上加上一个队列优化,减少了冗余的松弛操作,是一种高效的最短路算法。

 

算法大致思路:

  s表示源点

  利用dist[x]表示从源点s到x的最短距离

  用Q队列来保存需要处理的结点

  用inQueue[x]保存点x是否在队列中

  初始化:dist[]数组全部赋值为无穷大,比如INT_MAX(一定要足够大, 我一开始就是给小了所以有些数据错了)

  dist[s] = 0

开始算法:队列+松弛操作

  读取Q队首元素并出队(记得把inQueue[Q.top()]置为false)

  对与队首结点相连的所有点v进行松弛操作(如果源点通过队首结点再到结点v的距离比源点直接到v的距离要短,就更新dist[v],并且如果inQueue[v] == false 即V当前不在队列中,则v入队,当队列Q为空时,判断结束)

 

代码如下:

    #include<cstdio>
#include
<iostream>
#include
<cstring>
#include
<queue>
using namespace std;
const int MAXN = 20001;
const int MAXL = 200001;
const int INF = INT_MAX;
int dist[MAXN]; //dist[x]表示从源点到x所需的最短距离,初始为INF
int head[MAXN];
int M; //边的索引
bool inQueue[MAXN];
queue
<int> Q; //队列Q用来存放可松弛周围结点的结点
struct Edge{
int value;
int to;
int next;
}edge[MAXL];
//采用链式前向星存储边集

//构建边集合
void add(int from, int to, int value){
edge[M].to
= to;
edge[M].next
= head[from];
edge[M].value
= value;
head[
from] = M++;
}

//SPFA算法
void SPFA(int start){
dist[start]
= 0; //源点到自己的距离为0
Q.push(start);
inQueue[start]
= true;
while (!Q.empty()){
int temp = Q.front(); //取队头元素
Q.pop();
for (int j = head[temp]; j != -1; j = edge[j].next){
int toNode = edge[j].to;
if (dist[toNode] > dist[temp] + edge[j].value){ //本题保证无负环,否则需要利用一个数组判断j是否入队超过n次
dist[toNode] = dist[temp] + edge[j].value;
if (!inQueue[toNode]){
Q.push(toNode);
inQueue[toNode]
= true;
}
}
}
inQueue[temp]
= false;
}
}
int main(){
memset(head,
-1, sizeof(head));
int n, m;
scanf(
"%d%d", &n, &m);
for (int i = 1; i <= n; i++){ //初始化
dist[i] = INF;
inQueue[i]
= false;
}
for (int p = 1; p <= m; p++){
int from, to, value;
scanf(
"%d%d%d", &from, &to, &value); //用cin速度好像要慢一倍= =
add(from, to, value);
}
SPFA(
1);
for (int x = 2; x <= n; x++){
printf(
"%d\n", dist[x]);
}
return 0;
}