0pts 求助
查看原帖
0pts 求助
1003851
dsfgsdf楼主2025/7/20 21:49

打了一个dijkstra板子,却不知道哪打错了,大佬帮忙看下,谢谢

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
const int M=5*1e5+5;
struct node{
	int u,v,w;
};
vector<node>e[N];
int n,m,s,vis[N],dis[N],u1,v1,w1;
void dijkstra(){
	for(int i=1;i<=n;i++)dis[i]=1<<15;
	dis[s]=0;
	for(int i=1;i<=n;i++){
		int p=0,minn=1<<31;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&dis[j]<minn){
				minn=dis[j];
				p=j;
			}
		} 
		vis[p]=1;
		for(auto y:e[p]){
			if(dis[y.v]>dis[y.u]+y.w){
				dis[y.v]=dis[y.u]+y.w;
			}
		}
	} 
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>u1>>v1>>w1;
		e[u1].push_back({u1,v1,w1});
	}
	dijkstra();
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	return 0;
}

2025/7/20 21:49
加载中...