多源最短路 - 虚拟源点

March 3, 2023

790 views

1095 words

堆优化 + 虚拟源点

连一条到目标距离为 0 的路径

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

int n, m, q, k;
int dist[N];
int h[N], e[N], ne[N], w[N], idx;
bool st[N];
typedef pair<int, int> PII;

void add(int a, int b, int c){
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra(){
	priority_queue<PII, vector<PII>, greater<PII>> q;
	q.push({0, 0});
	dist[0] = 0;

while (!q.empty()) {
		auto t = q.top();
		q.pop();

int d = t.first, p = t.second;

if (st[p]) continue;
		st[p] = true;

for (int i = h[p]; ~i; i = ne[i]) {
			int j = e[i];
			if (dist[j] > d + w[i]) {
				dist[j] = d + w[i];
				q.push({dist[j], j});
			}
		}
	}
}

int main(){
	scanf("%d%d", &n, &m);

memset(h, -1, (n + 1) * 4);

int a, b, c;
	while (m--) {
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
		add(b, a, c);
	}

memset(dist, 0x3f, (n + 1) * 4);

scanf("%d", &k);
	while (k--) {
		scanf("%d", &a);
		add(0, a, 0);
		add(a, 0, 0);
	}

dijkstra();

scanf("%d", &q);

while (q--) {
		scanf("%d", &a);
		printf("%d\n", dist[a]);
	}

return 0;
}
```

Last modification：March 3, 2023

如果觉得我的文章对你有用，请随意赞赏