社区讨论
有没有人帮我康康这个Dijkstra最短路错在哪里
灌水区参与者 3已保存回复 15
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 14 条
- 当前快照
- 1 份
- 快照标识符
- @m3wsdft5
- 此快照首次捕获于
- 2024/11/25 16:48 去年
- 此快照最后确认于
- 2025/11/04 23:28 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
int v;
ll w;
edge(int vv,ll ww) {
v = vv;
w = ww;
return;
}
};
struct node{
int id;
ll dis;
node(int idd,ll diss) {
id = idd;
diss = dis;
return;
}
bool operator<(node xx) const{//小根堆
return dis > xx.dis;
}
};
int n,m,s;
vector<edge> g[100010];
ll dis[100010];
bool vis[100010];
priority_queue<node> q;
void Dijkstra() {
memset(dis,0x3f,sizeof(dis));
dis[s] = 0;
q.push(node(s,0));
while (!q.empty()) {
node u = q.top();
q.pop();
if (vis[u.id]) continue;//
vis[u.id] = true;//
for (int i = 0;i < g[u.id].size();i ++) {
int v = g[u.id][i].v;
ll w = g[u.id][i].w;
if (dis[v] > u.dis + w) {
dis[v] = u.dis + w;
q.push(node(v,dis[v]));
}
}
}
return;
}
int main() {
scanf("%d%d%d",&n,&m,&s);
for (int i = 1;i <= m;i ++) {
int ut,vt;
ll wt;
scanf("%d%d%lld",&ut,&vt,&wt);
g[ut].push_back(edge(vt,wt));
}
Dijkstra();
for (int i = 1;i <= n;i ++)
if (dis[i] == 0x3f3f3f3f3f3f3f3fll) printf("2147483647 ");
else printf("%lld ",dis[i]);
printf("\n");
return 0;
}
回复
共 15 条回复,欢迎继续交流。
正在加载回复...