社区讨论

Help!恳请各位大佬帮忙 help

P4779【模板】单源最短路径(标准版)参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lw9je9u1
此快照首次捕获于
2024/05/17 01:40
2 年前
此快照最后确认于
2024/05/17 15:07
2 年前
查看原帖
错了1 3 4
CPP
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;

const int w = 1e5 + 5;
struct P{
	int x, y, v;
	bool operator<(const P &other) const {
		return v > other.v;
	}
	//按v来排序的优先队列
}p;
priority_queue<P> q;
int mark[w], ans[w];
vector<int> a[w], b[w];
int main()//4779
{
	int n, m, i, s, x, y, v;
	cin >> n >> m >> s;
	for (i = 1; i <= n; i++) ans[i] = 1e9;
	while (m--) {
		cin >> x >> y >> v;
		a[x].push_back(y);
		b[x].push_back(v);
	}
	ans[s] = 0, mark[s] = 1;
	
	//先把第一个点所能到的入队
	for (i = 0; i < a[s].size(); i++) {
		int l = a[s][i];
		ans[l] = min(ans[l], ans[s] + b[s][i]);
		q.push({ s,a[s][i],b[s][i] });
	}
	//dij(因为先上面先入队一次,下面用p.y)
	while (q.size()) {
		p = q.top();
		q.pop();
		if (mark[p.y]) continue;
		mark[p.y] = 1;
		for (i = 0; i < a[p.y].size(); i++) {
			int l = a[p.y][i];
			if (mark[l]) continue;
			ans[l] = min(ans[l], ans[p.y] + b[p.y][i]);
			q.push({p.y,l,b[p.y][i]});
		}
	}
	for (i = 1; i <= n; i++) cout << ans[i] << " ";
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...