Dusk777 @ 2024-06-01 10:59:03
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const long long inf = 2147483647;
struct adjnode {
ll goal;
ll w;
};
int main() {
ll n, m, s;
cin >> n >> m >> s;
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
vector<vector<adjnode>> adj(n + 1);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> heap;
vector<ll> dist(n + 1, inf);
vector<ll> vis(n + 1, 1);
for (int i = 1; i <= m; i++) {
ll u, v, w;
cin >> u >> v >> w;
adjnode tmp;
tmp.goal = v;
tmp.w = w;
adj[u].push_back(tmp);
}
dist[s] = 0;
vis[s] = 0;
heap.push({0, s});
while (!heap.empty()) {
ll start = heap.top().second;
heap.pop();
for (int i = 0; i < adj[start].size(); i++) {
adjnode next = adj[start][i];
ll new_dist = dist[start] + next.w;
if (new_dist < dist[next.goal]) {
dist[next.goal] = new_dist;
heap.push({dist[next.goal], next.goal});
}
}
}
for (int i = 1; i <= n; i++) {
cout << dist[i];
if (i != n) {
cout << " ";
}
}
return 0;
}
by DrAlfred @ 2024-06-01 11:22:36
@Dusk777 你的 Dijkstra 更新了一些无用的点。
每次拿出 start 之后要判断一下:
ll start = heap.top().second, w = heap.top().first;
heap.pop();
if (dis[start] != w) {
continue;
}
by Genius_Star @ 2024-06-01 11:22:52
您的 vis 数组是用来给谁看的?
by DrAlfred @ 2024-06-01 11:23:47
笔误,dist
by Dusk777 @ 2024-06-01 15:40:52
@DrAlfred 咱们的意思是如果从heap中拿出的点已经不是dist中的最短路了,就跳过本次循环吗,感谢,我似乎理解了
by Dusk777 @ 2024-06-01 15:43:07
@Genius_Star 抱歉,之前做弱化版时考虑的普通diji没有使用堆,采用vis标记已经访问过的节点,但是在这里不知道如何讨论vis数组,同时又忘记删去了,故混进无用的数据