本人找了无数次,都没找到我的代码哪里错了
查看原帖
本人找了无数次,都没找到我的代码哪里错了
973280
Apollo0130楼主2024/7/11 15:06

我不就打了一个Dijstra吗,至于让我10个WA吗

#include<bits/stdc++.h>
using namespace std;
const int N=25005,M=65005;
int h[N],e[M],ne[M],w[M],idx,dist[N];
int n,m,s,ee;
bool st[N];
void add(int a,int b,int c){
	e[idx]=a,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dijkstra(int u){
	memset(dist,0x3f,sizeof(dist));
	dist[u]=0;
	for(int i=0;i<n;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[t] && (t==-1 || dist[t]>dist[j]))t=j;
		}
		st[t]=true;
		if(t==ee)break;
		for(int j=h[t];~j;j=ne[j]){
			int y=e[j];
			dist[y]=min(dist[y],dist[t]+w[j]);
		}
	}
	return dist[ee];
}
int main(){
	memset(h,-1,sizeof(h));
	cin>>n>>m>>s>>ee;
	int x,y,z;
	while(m--){
		cin>>x>>y>>z;
		add(x,y,z);add(y,x,z);
	}
	cout<<dijkstra(s);
	return 0;
}
2024/7/11 15:06
加载中...