【洛谷P3371】【模板】单源最短路径（弱化版） 解题报告

洛谷P3371 - 【模板】单源最短路径（弱化版）

题目背景

本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 $n,m,s$，分别表示点的个数、有向边的个数、出发点的编号。

接下来 $m$ 行每行包含三个整数 $u,v,w$，表示一条 $u\to v$ 的，长度为 $w$ 的边。

输出格式

输出一行 $n$ 个整数，第 $i$ 个表示 $s$ 到第 $i$ 个点的最短路径，若不能到达则输出 $2^{31}-1$。

样例 #1

样例输入 #1

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

样例输出 #1

0 2 4 3

提示

【数据范围】
对于 $20\%$ 的数据：$1\le n\le 5$，$1\le m\le 15$；
对于 $40\%$ 的数据：$1\le n\le 100$，$1\le m\le 10^4$；
对于 $70\%$ 的数据：$1\le n\le 1000$，$1\le m\le 10^5$；
对于 $100\%$ 的数据：$1\le n\le 10^4$，$1\le m\le 5\times 10^5$，$1\le u,v\le n$，$w\ge 0$，$\sum w<2^{31}$，保证数据随机。

Update 2022/07/29：两个点之间可能有多条边，敬请注意。

对于真正 $100\%$ 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。

样例说明：

图片1到3和1到4的文字位置调换

这题虽说是一道单源最短路径的板子题，但是还是调了我三天左右，心态真的有点爆炸。
好在终于给我调出来了，有种当年打$OI$时候的美。话说408考研初试好像要求没这么高，我是不是有点在浪费时间……
嘛，话不多说，先分析题目。
题面非常简单，就是给你一个带权有向图，输入点数、边数、起始点（源点），然后输入每一条弧的起点和终点，以及弧的权值。
需求是输出这个源点到其他所有点的最短路径长度（当然，到它自己就是$0$）。
看一眼数据，点数$n$的范围有$10^4$数量级，所以不能用邻接矩阵存图 ，除非你只要40分 。于是我用了邻接表存图，并且偷懒直接用自己之前写的板子。我看很多题解似乎都是用静态链表存的，那么我贴一个动态链表的写法。
相关知识点请参阅我的另一篇博客：图的存储与基本操作
预定义代码如下：

#define MaxVertexNum 10007
#define INF 0x7fffffff

typedef struct ArcNode {
	int adjvex, info;
	struct ArcNode* nextarc;
}ArcNode, * ArcList;
typedef struct VNode {
	int data;
	ArcNode* firstarc;
}VNode, AdjList[MaxVertexNum];
typedef struct {
	AdjList vertices;
	int vexnum, arcnum, Start;
}ALGraph;
//图的邻接表存储表示法

然后是图的基本操作，对邻接表存储表示法存储的带权有向图，加入一条弧的写法也非常简单，只需使用$malloc$函数给一个新结点，存入弧尾以及弧长，然后使用头插法加入弧头顶点的边表即可。
我也直接偷懒，用了另一道模板题里的插入函数和预处理函数，稍作修改。
请参阅我另一篇博客：【洛谷B3643】图的存储 解题报告

inline void AG_Insert(ALGraph& G, int i, int j, int k) {
	ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
	p->adjvex = j;
	p->info = k;
	ArcNode* head = G.vertices[i].firstarc;
	ArcNode* tail = G.vertices[i].firstarc->nextarc;
	p->nextarc = tail;
	head->nextarc = p;
	return;
}

然后就是核心部分，$Dijkstra$算法求解单源最短路径问题。这题经过测试，可以使用朴素迪杰，无需用堆或者优先队列优化（如果打$OI$或者$ACM$还是学下比较好，不过毕竟我只是个考研的，就不学了）。

关于$Dijkstra$算法，请参阅我的另一篇博客，内有详细讲解：图的应用2-最短路径

不过也就是这个迪杰斯特拉，调了我三天（准确来说是三个晚上），从$WA(30pts)->TLE(10pts)->RE(60pts)->WA(60pts)$，最后才到$AC(100pts)$。
题目里有的坑，我都踩过了。
首先是两点之间存在多条弧，这点在读入的时候，让$dist[i]$与读入值作比取其小就行。
然后是朴素迪杰的一些玄学问题，在循环处理各点的时候，如果已经处理完而还未执行完循环，就会出现$RE$的问题。我也不知道为何，总之加了个条件判断$break$之后就好了。当然，这些问题也是根据$std$数据才找出来的。
预处理函数和主函数如下：

inline void Init(ALGraph& G) {
	for (int i = 1; i <= G.vexnum; ++i) {
		ArcList h = (ArcList)malloc(sizeof(ArcList));
		h->adjvex = -1;
		h->info = INF;
		h->nextarc = NULL;
		G.vertices[i].data = i;
		G.vertices[i].firstarc = h;//对顶点表的预处理
		final[i] = false, dist[i] = INF, path[i] = -1;
		//访问标记数组，距离数组，路径数组（这个这题其实用不上但我还是写了）
	}
	return;
}

int main() {
	ALGraph G;
	cin >> G.vexnum >> G.arcnum >> G.Start;
	Init(G);//预处理
	int u, v, w;
	for (int i = 1; i <= G.arcnum; ++i) {
		cin >> u >> v >> w;
		AG_Insert(G, u, v, w);
		if (u == G.Start)dist[v] = min(dist[v], w), path[v] = u;
		//处理两点之间存在多条弧的情况，取最短的弧
		//实际上我只处理了和源点相连的弧，但是这样也能过
		//所以说数据还是比较水的
	}
	Dijkstra(G);//执行迪杰斯特拉算法
	for (int i = 1; i <= G.vexnum; ++i) {//输出
		cout << dist[i];
		if (i < G.vexnum)cout << " ";
		else cout << endl;
	}
	return 0;
}

然后是 $Dijkstra$算法的执行函数 ：我感觉不太完善，如果有改进意见还请指出。

inline void Dijkstra(ALGraph G) {
	int u = G.Start, v, w, n = G.vexnum;
	//一些临时变量（弧头，弧尾，权值，循环次数常量）
	final[u] = true, dist[u] = 0;
	//源点访问标记true，dist置零
	while (n--) {
		int minn = INF, minm = 0;//dist的最小值和该点编号
		for (int i = 1; i <= G.vexnum; ++i) {
			if (!final[i])
				if (dist[i] < minn)minn = dist[i], minm = i;
				//找到未访问的点里dist值最小的点
		}
		if (minn == INF)break;//如果全都访问过那minn就是INF不变，直接跳出
		final[minm] = true;//已访问标记
		u = minm;//开始处理该点所有邻边
		for (ArcNode* p = G.vertices[u].firstarc->nextarc; p != NULL; p = p->nextarc) {
			v = p->adjvex, w = p->info;
			if (dist[v] > dist[u] + w)//更新u所有邻边连接的点的dist值保证找到最小
					dist[v] = dist[u] + w, path[v] = u;
		}
	}
	return;
}

最后贴一下完整的AC代码：“吸了氧”（开启$O2$加速）过的（$1.71s$），不知道不吸氧能不能过。

//AC(100pts)
#define _CRT_SECURE_NO_WARNINGS 1
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define MaxVertexNum 10007
#define MaxMGSize 500007
#define INF 0x7fffffff

typedef struct ArcNode {
	int adjvex, info;
	struct ArcNode* nextarc;
}ArcNode, * ArcList;
typedef struct VNode {
	int data;
	ArcNode* firstarc;
}VNode, AdjList[MaxVertexNum];
typedef struct {
	AdjList vertices;
	int vexnum, arcnum, Start;
}ALGraph;

bool final[MaxVertexNum];
int dist[MaxVertexNum], path[MaxVertexNum];

inline void Init(ALGraph& G) {
	for (int i = 1; i <= G.vexnum; ++i) {
		ArcList h = (ArcList)malloc(sizeof(ArcList));
		h->adjvex = -1;
		h->info = INF;
		h->nextarc = NULL;
		G.vertices[i].data = i;
		G.vertices[i].firstarc = h;
		final[i] = false, dist[i] = INF, path[i] = -1;
	}
	return;
}

inline void AG_Insert(ALGraph& G, int i, int j, int k) {
	ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
	p->adjvex = j;
	p->info = k;
	ArcNode* head = G.vertices[i].firstarc;
	ArcNode* tail = G.vertices[i].firstarc->nextarc;
	p->nextarc = tail;
	head->nextarc = p;
	return;
}

inline void Dijkstra(ALGraph G) {
	int u = G.Start, v, w, n = G.vexnum;
	final[u] = true, dist[u] = 0;
	while (n--) {
		int minn = INF, minm = 0;
		for (int i = 1; i <= G.vexnum; ++i) {
			if (!final[i])
				if (dist[i] < minn)minn = dist[i], minm = i;
		}
		if (minn == INF)break;
		final[minm] = true;
		u = minm;
		for (ArcNode* p = G.vertices[u].firstarc->nextarc; p != NULL; p = p->nextarc) {
			v = p->adjvex, w = p->info;
			if (dist[v] > dist[u] + w)
					dist[v] = dist[u] + w, path[v] = u;
		}
	}
	return;
}

int main() {
	ALGraph G;
	cin >> G.vexnum >> G.arcnum >> G.Start;
	Init(G);
	int u, v, w;
	for (int i = 1; i <= G.arcnum; ++i) {
		cin >> u >> v >> w;
		AG_Insert(G, u, v, w);
		if (u == G.Start)dist[v] = min(dist[v], w), path[v] = u;
	}
	Dijkstra(G);
	for (int i = 1; i <= G.vexnum; ++i) {
		cout << dist[i];
		if (i < G.vexnum)cout << " ";
		else cout << endl;
	}
	return 0;
}

完整代码也可看我的Github：传送门

总之，虽然408考研初试要求似乎没这么高，但是我还是有点一时上头，把这个题给打了。以前打$OI$的时候其实已经$AC$过这题了，但是代码似乎只是把别人的看懂然后随便改了改就当成自己的交了。孩子们，不要学我，不然未来是一定会吃亏的……
以上。