C++ – Dijskra原理 模板

原理

https://blog.csdn.net/alexfaker/article/details/90199074

模板

https://www.cnblogs.com/iloveori/p/12526461.html#%E8%A7%82%E5%89%8D%E6%8F%90%E7%A4%BA%EF%BC%9A%E8%AF%B7%E4%B8%8D%E8%A6%81%E5%9C%A8%E8%B4%9F%E6%9D%83%E5%9B%BE%E4%B8%AD%E7%86%9F%E7%BB%83%E7%9A%84%E8%BF%90%E7%94%A8%E8%BF%99%E4%B8%AA%E7%AE%97%E6%B3%95%E3%80%82

个人模板

https://www.luogu.com.cn/problem/P4779

#include
#include
#include
#include
#include
#include
#include
#define go(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
int n, m, s, u, v, w, vis[100010], dis[100010];
struct ed {
	int v, w;
};
vector vec[100010];
priority_queue, vector >, greater > > q;
void dij(int x) {
	dis[x] = 0;
	q.push({ 0,x });
	while (!q.empty()) {
		pair head = q.top();
		q.pop();
		if (vis[head.second])
			continue;
		vis[head.second] = 1;
		int len = vec[head.second].size();
		go(i, 0, len - 1) {
			if (dis[vec[head.second][i].v] > dis[head.second] + vec[head.second][i].w) {
				dis[vec[head.second][i].v] = dis[head.second] + vec[head.second][i].w;
				q.push({ dis[vec[head.second][i].v],vec[head.second][i].v });
			}
		}
	}
}
int main() {
	cin >> n >> m >> s;
	memset(dis, 0x7f, sizeof dis);
	go(i, 1, m) {
		int x, y, z;
		ed tmp;
		cin >> x >> y >> z;
		tmp.v = y;
		tmp.w = z;
		vec[x].push_back(tmp);
	}
	dij(s);
	go(i, 1, n)
		cout << dis[i] << ' ';
	return 0;
}

发表回复