dijkstra算法+链表储存+优先队列

原题链接

P4779 【模板】单源最短路径（标准版）

ac代码

#include <iostream>
#include <queue>

using namespace std;
const int MAXN = 100010, MAXM = 500010;

struct edge
{
	int to;
	int dis;
	int next;//链表的下一个
} e[MAXM];

int head[MAXN], dis[MAXN];
bool vis[MAXN];
int n, m, s;//n为点数，m为边数，s为起点
int cnt = 0;//edge个数

struct node
{
	int dis;//储存距离
	int pos;//储存下标
	bool operator < (const node& x)const 
	{
		return x.dis < dis;//优先队列从小到大排列
	}
};

priority_queue<node> q;//优先队列

void dijkstra()
{
	dis[s] = 0;
	node a = { 0, s };
	q.push(a);
	while (!q.empty())
	{
		node tmp = q.top();
		q.pop();
		int x = tmp.pos, d = tmp.dis;
		if (!vis[x])//未访问过
		{
			vis[x] = true;
			for (int i = head[x]; i; i = e[i].next)//遍历与x相连的所有结点
			{
				int y = e[i].to;
				if (dis[y] > dis[x] + e[i].dis)//比较，更新
				{
					dis[y] = dis[x] + e[i].dis;
					if (!vis[y])//更新的结点未访问过，加入队列
					{
						node a = { dis[y], y };
						q.push(a);
					}
				}
			}
		}
	}
}


int main()
{
	cin >> n >> m >> s;//n为点数，m为边数，s为起点

	for (int i = 1; i <= n; ++i)
		dis[i] = 0x7fffffff;//初始化

	for (int i = 0; i < m; ++i)
	{
		int u, v, d;//u到v之间有一条权值为d的有向边
		cin >> u >> v >> d;
		++cnt;
		e[cnt].dis = d;
		e[cnt].to = v;
		e[cnt].next = head[u];//链表储存，头插法，存的是e数组下标
		head[u] = cnt;
	}//存图

	dijkstra();

	for (int i = 1; i <= n; ++i)
		cout << dis[i] << ' ';//输出
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86