社区讨论

求助大佬

P3371【模板】单源最短路径(弱化版)参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo2w824h
此快照首次捕获于
2023/10/23 20:47
2 年前
此快照最后确认于
2023/10/23 20:47
2 年前
查看原帖
CPP
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=0x3f3f3f3f;
struct Edge {
	int son,father,dis;
} edge[1000000];
int head[20000],cnt,ans[20000];
bool vis[20000];
long long minn=maxn;
inline void add_edge(int q,int z,int dis) {
	cnt++;
	edge[cnt].son=z,edge[cnt].dis=dis,edge[cnt].father=head[q],head[q]=cnt;
}
int n,m,s,a,b,c
int main() {
	ios::sync_with_stdio(0);
	cin>>n>>m>>s;
	memset(ans,maxn,sizeof(ans));
	for(int i=1; i<=m; i++) {
		cin>>a>>b>>c;
		add_edge(a,b,c);
	}
	int curr=s;
	ans[s]=0;
	while(!vis[curr]) {
		vis[curr]=1;
		for(int i=head[curr]; i!=0; i=edge[i].father) {
			if(!vis[edge[i].son]&&ans[edge[i].son]>ans[curr]+edge[i].dis) {
				ans[edge[i].son]=ans[curr]+edge[i].dis;
			}
		}
		minn=maxn;
		for(int i=1; i<=n; i++) {
			if(!vis[i]&&minn>ans[i]) {
				minn=ans[i];
				curr=i;
			}
		}
	}
	for(int i=1; i<=n; i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}
为什么会WA一个点啊?

回复

1 条回复,欢迎继续交流。

正在加载回复...