1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 using namespace std;
6 int head[
1000005],n, m, cnt, ccnt;
7 long long dist[
1000005],ans;
8 struct pot {
9 int id;
10 int val;
11 bool operator<(
const struct pot&aa)
const {
12 return val >
aa.val;
13 }
14 };
15 struct edge {
16 int fr;
17 int to;
18 long long v;
19 int next;
20 }e[
1000005];
21 void INIT() {
22 memset(head, -
1,
sizeof(head));
23 memset(dist,
0x3f3f3f3f,
sizeof(dist));
24 dist[
1] =
0;
25 cnt=
0;
26 ans =
0;
27 }
28 void adde(
int xx,
int yy,
long long zz) {
29 e[cnt].fr =
xx;
30 e[cnt].to =
yy;
31 e[cnt].v =
zz;
32 e[cnt].next =
head[xx];
33 head[xx] = cnt++
;
34 }
35 void dij() {
36 priority_queue<
struct pot>
pq;
37 struct pot sta;
38 sta.id =
1;
39 sta.val =
0;
40 pq.push(sta);
41 while (!
pq.empty()) {
42 struct pot aa =
pq.top(); pq.pop();
43 if (dist[aa.id] < aa.val)
continue;
44 for (
int i = head[aa.id]; i != -
1; i =
e[i].next) {
45 if (dist[e[i].to] > dist[aa.id] +
e[i].v) {
46 dist[e[i].to] = dist[aa.id] +
e[i].v;
47 struct pot cc;
48 cc.id =
e[i].to;
49 cc.val =
dist[e[i].to];
50 pq.push(cc);
51 }
52 }
53 }
54 }
55 int main() {
56 int t;
57 scanf(
"%d",&
t);
58 while (t--
) {
59 INIT();
60 scanf(
"%d%d", &n, &
m);
61 while (m--
) {
62 int x, y;
63 long long z;
64 scanf(
"%d%d%lld", &x, &y, &
z);
65 adde(x, y, z);
66 }
67 dij();
68 }
69 return 0;
70 }
转载于:https://www.cnblogs.com/MekakuCityActor/p/8987593.html
