帮我写一段dijsktra代码
时间: 2023-12-26 13:52:26 浏览: 30
好的,下面是一段Dijkstra算法的代码,可以用来解决最短路径问题:
```
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 10005;
int n, m, u[MAXN], v[MAXN], w[MAXN], dis[MAXN], vis[MAXN], cnt = 0;
int head[MAXN], nxt[MAXN], to[MAXN], edge[MAXN];
void add_edge(int u, int v, int w){
cnt++;
to[cnt] = v;
edge[cnt] = w;
nxt[cnt] = head[u];
head[u] = cnt;
}
void dijkstra(int s){
memset(dis, INF, 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(make_pair(dis[s], s));
while(!q.empty()){
int x = q.top().second;
q.pop();
if(vis[x]) continue;
vis[x] = 1;
for(int i = head[x]; i; i = nxt[i]){
int y = to[i], z = edge[i];
if(dis[y] > dis[x] + z){
dis[y] = dis[x] + z;
if(!vis[y]){
q.push(make_pair(dis[y], y));
}
}
}
}
}
int main(){
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++){
scanf("%d %d %d", &u[i], &v[i], &w[i]);
add_edge(u[i], v[i], w[i]);
}
dijkstra(1);
for(int i = 1; i <= n; i++){
printf("%d ", dis[i]);
}
return 0;
}
```
以上代码实现了Dijkstra算法的核心部分,具体用法可参考main函数中的测试数据。但请注意,Dijkstra算法并不是万能的,它只能用来求解带非负权值的最短路径问题。如有需要,您可以在此基础上进行适当的改进。