社区讨论

求助,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 条回复,欢迎继续交流。

正在加载回复...