PTA Dijkstra算法（模板） (30分)

给一个n(1 ≤ n ≤ 2500) 个点 m(1 ≤ m ≤ 6200) 条边的无向图，求 s 到 t 的最短路。

输入格式:

第一行四个由空格隔开的整数 n、m、s、t。

之后的 m 行，每行三个正整数 s​i​​ 、t​i​​ 、w​i​​ (1≤w​i​​ ≤10​9​​ )，表示一条从s​i​​ 到 t​i​​ 长度为 w​i​​ 的边。

输出格式:

一个整数，表示从s 到t 的最短路径长度。数据保证至少存在一条道路。

输入样例:

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
1
2
3
4
5
6
7
8
9
10
11
12

输出样例:

7
1

注意:

两个顶点之间可能存在多条直接相连的道路。
顶点数与边数在同一级别，用邻接表存储

代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 2505;
typedef long long ll;
ll dist[maxn];
bool vis[maxn];

struct node{
	int i;
	ll Weight;
};

struct cmp{
	bool operator() (const node n1, const node n2){
		return n1.Weight > n2.Weight;
	}
};

typedef struct ENode{
	int v1, v2;
	ll Weight;
} * Edge;

struct AdjVNode{
	int AdjV;
	ll Weight;
	AdjVNode *Next;
};
typedef struct VNode{
	AdjVNode *FirstEdge;
} AdjList[maxn];
typedef struct GNode{
	int Nv, Ne;
	AdjList L;
} * Graph;

void InsertEdge(Graph G, Edge E)
{
	AdjVNode *A;
	A = new AdjVNode;
	A->AdjV = E->v2, A->Weight = E->Weight;
	A->Next = G->L[E->v1].FirstEdge;
	G->L[E->v1].FirstEdge = A;

	A = new AdjVNode;
	A->AdjV = E->v1, A->Weight = E->Weight;
	A->Next = G->L[E->v2].FirstEdge;
	G->L[E->v2].FirstEdge = A;
}

void Dijkstra(Graph G, int s)
{
	priority_queue<node, vector<node>, cmp> q;
	memset(dist, 0x3f, sizeof(dist));
	dist[s] = 0;
	q.push({s, dist[s]});

	AdjVNode *A;
	while (!q.empty())
	{
		int v = q.top().i;
		q.pop();
		if(vis[v])
			continue;
		vis[v] = true;

		A = G->L[v].FirstEdge;
		while (A)
		{
			if(!vis[A->AdjV])
				if(dist[v] + A->Weight < dist[A->AdjV])
					dist[A->AdjV] = dist[v] + A->Weight, q.push({A->AdjV, dist[A->AdjV]});
			A = A->Next;
		}
	}
}
void Destroy(Graph G)
{
	AdjVNode *A;
	for (int i = 1; i <= G->Nv; i++)
		while (G->L[i].FirstEdge)
		{
			A = G->L[i].FirstEdge;
			G->L[i].FirstEdge = A->Next;
			delete A;
		}
	delete G;
}

int main()
{
	int n, m, s, t;
	cin >> n >> m >> s >> t;
	Graph G = new GNode();
	G->Nv = n, G->Ne = m;

	Edge E = new ENode;
	for (int i = 0; i < m; i++)
	{
		cin >> E->v1 >> E->v2 >> E->Weight;
		InsertEdge(G, E);
	}
	delete E;
	Dijkstra(G, s);
	cout << dist[t] << endl;
	Destroy(G);

	system("pause");
	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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

C++优先队列的用法: https://blog.csdn.net/disguise666/article/details/85989788