社区讨论
求助,dijkstra模板写得哪里有问题
灌水区参与者 5已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @lran6a34
- 此快照首次捕获于
- 2024/01/12 20:55 2 年前
- 此快照最后确认于
- 2024/01/13 08:04 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f;
int mp[1010][1010],vis[1010],d[1010],n;
void dijkstra(){
memset(d,INF,sizeof(d));
d[1]=0;
for(int step=1;step<=n;step++){
int mi=INF;
int id=-1;
for(int i=1;i<=n;i++){
if(d[i]<=mi&&!vis[i]){
mi=d[i];
id=i;
}
}
vis[id]=1;
for(int i=1;i<=n;i++){
if(d[id]+mp[id][i]<d[i]){
d[i]=d[id]+mp[id][i];
}
}
}
printf("%d\n",d[n]);
}
int main(){
memset(mp,INF,sizeof(mp));
int m;
scanf("%d%d",&n,&m);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
mp[a][b]=mp[b][a]=min(mp[a][b],c);
}
dijkstra();
return 0;
}
回复
共 11 条回复,欢迎继续交流。
正在加载回复...