蓝桥杯 ALGO-5 最短路

题目

问题描述
给定一个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，保证从任意顶点都能到达其他所有顶点。

题解

题目有负的权值，不能用 Dijkstra 算法
用 SPFA算法
还要优化过
设置队列，每次入队相邻结点，判断距离是否更近，如果距离更近将该相邻结点入队列，直到队列为空。可在相邻结点进行处理，设置数组 head 存储相邻点编号，边存储相同起点的下一边编号，这样找邻接点更快

未优化版本
只有70分，但是相对好理解些

#include<queue>
#include<cstdio>
#include<string.h>
using namespace std;
const int MAXM = 200005;
const int MAXN = 20005;
const int INF = 99999999;
struct Edge{  // 边信息 
	int sta; // 起点 
	int des; // 终点
	int val;  // 权值 
}e[MAXM];
int n; // 点 
int m; // 边 
int dis[MAXN]={0};  // 距离 
bool visit[MAXM] = {false}; // 记录点的访问状态 

void Init(){
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;i++)
		dis[i] = INF;
	for(int i=0;i<m;i++)
		scanf("%d%d%d",&e[i].sta,&e[i].des,&e[i].val);
}

void SPFA(){
	queue<int> q;
	q.push(1);  // 第一个点入队列 
	visit[1] = true;  // 改变访问状态
	int f; // 队列第一个元素
	while(!q.empty()){
		f = q.front();
		q.pop();
		visit[f] = false;  // 已经取出来了
		for(int i=0;i<m;i++){  // 遍历以 f 为起点的所有值 
			if(e[i].sta == f){
				// i 到 j 有边
				// 如果 1 到 j 的距离比 1 到i + i到 j 的距离更大，更新距离 
				if(dis[e[i].des] > dis[e[i].sta]+e[i].val){   
					dis[e[i].des] = dis[e[i].sta]+e[i].val;
					if(!visit[e[i].des]){ // 如果当前点不在队列，入队 
						q.push(e[i].des);
						visit[e[i].des] = true;
					}
				} 
			}
		}			 
	}
}

int main(){
	Init();
	SPFA();
	for(int i=2;i<=n;i++)
		printf("%d\n",dis[i]);
	return 0;
} 

优化版本
增加了 head 数组快速查找相邻结点

#include<queue>
#include<cstdio>
#include<string.h> 
using namespace std;
const int MAXM = 200100;
const int MAXN = 21000;
const int INF = 99999999;
struct Edge{  // 边信息 
	int sta; // 起点 
	int des; // 终点
	int val;  // 权值 
	int next;  // 相同起点的下一条边编号 
}e[MAXM];
int n; // 点 
int m; // 边 
int dis[MAXN];  // 距离 
bool visit[MAXN]; // 记录点的访问状态 
int head[MAXN];  // 建立一条伪链表，head[i] 表示以点 i 为起点的边的编号 
using namespace std;

void Init(){
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;i++){ 
		dis[i] = INF;
		visit[i] = false;
	} 
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&e[i].sta,&e[i].des,&e[i].val);
		e[i].next = head[e[i].sta];
		head[e[i].sta] = i;
	}
}

void SPFA(){
	queue<int> q;
	q.push(1);  // 第一个点入队列 
	visit[1] = true;  // 入队改变状态 
	dis[1] = 0;
	int f; // 队列第一个元素
	while(!q.empty()){
		f = q.front();
		q.pop();
		visit[f] = false;  // 已经取出来了
		for(int i=head[f];i!=-1;i=e[i].next){  // 遍历以 f 为起点的所有值 
			// i 到 j 有边
			// 如果 1 到 j 的距离比 1 到i + i到 j 的距离更大，更新距离 
			if(dis[e[i].des] > dis[f]+e[i].val){   
				dis[e[i].des] = dis[f]+e[i].val;
				if(!visit[e[i].des]){ // 如果当前点不在队列，入队 
					q.push(e[i].des);
					visit[e[i].des] = true;
				}
			}
		}		
	}
}


int main(){
	Init();
	SPFA();
	for(int i=2;i<=n;i++)
		printf("%d\n",dis[i]); 
	return 0;
}