1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void dijkstra() {
	for (int i = 1; i <= n; i++) {
		int mink = 0;
		for (int j = 1; j <= n; j++) {
			if (!vis[j] && d[j] <= d[mink]) {
				mink = j;
			}
		}
		vis[mink] = true;
		for (Edge &e : g[mink]) {
			if (d[mink] < d[e.v] && d[mink] + e.w < d[e.v]) {
				d[e.v] = d[mink] + e.w;
			}
		}
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

void dijkstra() {
	while (!q.empty()) {
		int x = q.top().id;
		q.pop();
		if (!vis[x]) {
			vis[x] = true;
			for (Edge &e : g[x]) {
				if (d[e.v] > d[x] + e.w) {
					d[e.v] = d[x] + e.w;
					if (!vis[e.v]) {
						q.push({e.v, d[e.v]});
					}
				}
			}
		}
	}
}