GG_and_go_to_died @ 2023-10-12 20:40:31
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to;
int weight;
};
struct AdjList {
vector<Edge> edges;
};
void Dijkstra(vector<AdjList>& graph, int start, vector<int>& distance) {
int n = graph.size();
vector<bool> visited(n, false);
distance[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, start));
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
visited[u] = true;
for (const Edge& edge : graph[u].edges) {
int v = edge.to;
int weight = edge.weight;
if (!visited[v] && distance[u] + weight < distance[v]) {
distance[v] = distance[u] + weight;
pq.push(make_pair(distance[v], v));
}
}
}
}
int main() {
int n, m, s;
cin >> n >> m >> s;
vector<AdjList> graph(n + 1);
vector<int> distance(n + 1, INT_MAX);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].edges.push_back({v, w});
}
Dijkstra(graph, s, distance);
for (int i = 1; i <= n; i++) {
cout << distance[i] << " ";
}
cout << endl;
return 0;
}
by YiX01 @ 2023-10-12 20:41:53
你的节点就算被遍历过了,也要更新最短路吧。
by xuhanxi_dada117 @ 2023-10-12 20:45:53
在 pq.pop();
后面判一下:如果已经到过了(visited[u]
) 那么跳过。
by GG_and_go_to_died @ 2023-10-12 20:51:30
@xuhanxi_dada117 谢谢,大佬nb
by xuhanxi_dada117 @ 2023-10-12 20:55:18
我是蒟蒻。
by GG_and_go_to_died @ 2023-10-12 21:00:56
@xuhanxi_dada117 6