Dijkstra模板代码
时间: 2023-04-02 21:03:02 浏览: 75
以下是 Dijkstra 算法的模板代码:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 100005;
const int INF = x3f3f3f3f;
struct Edge {
int to, w;
Edge(int to, int w) : to(to), w(w) {}
};
vector<Edge> G[MAXN];
int d[MAXN];
bool vis[MAXN];
void dijkstra(int s) {
memset(d, INF, sizeof(d));
memset(vis, false, sizeof(vis));
d[s] = ;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(, s));
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = ; i < G[u].size(); i++) {
int v = G[u][i].to;
int w = G[u][i].w;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
pq.push(make_pair(d[v], v));
}
}
}
}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = ; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
G[u].push_back(Edge(v, w));
}
dijkstra(s);
for (int i = 1; i <= n; i++) {
cout << d[i] << " ";
}
cout << endl;
return ;
}
```
希望对你有帮助!