c++ 最短路线 源代码
时间: 2023-09-01 18:07:49 浏览: 32
以下是C++实现Dijkstra算法求最短路的示例代码:
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
struct Edge {
int v, w, nxt;
} e[N << 1];
int head[N], dis[N], vis[N], tot;
void addEdge(int u, int v, int w) {
e[++tot] = {v, w, head[u]};
head[u] = tot;
}
void dijkstra(int s) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({0, s});
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v, w = e[i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!vis[v]) q.push({dis[v], v});
}
}
}
}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
addEdge(u, v, w);
}
dijkstra(s);
for (int i = 1; i <= n; i++)
cout << (dis[i] == INF ? -1 : dis[i]) << ' ';
cout << endl;
return 0;
}
```
其中,变量`n`、`m`、`s`分别表示图中节点数、边数和起点编号。`addEdge()`函数用于向邻接表中添加边。`dijkstra()`函数实现Dijkstra算法。在主函数中读入图信息,调用`dijkstra()`函数求最短路,并输出结果。