社区讨论

求助0分，WA

奋奋斗吧！少女
P3371【模板】单源最短路径（弱化版）参与者 5已保存回复 8

讨论操作

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

当前回复
8 条
当前快照
1 份
快照标识符
@lobvsuhr
此快照首次捕获于
2023/10/30 03:46
2 年前
此快照最后确认于
2023/11/04 08:48
2 年前
查看原帖
这个代码错哪了？
CPP
#include<bits/stdc++.h>
using namespace std;
long long n,m,i,x,y,z,cf,j,mi,qi,a[1010][1010],f[10010],v[10010];
int main(){
	scanf("%lld%lld%lld",&n,&m,&qi);
	for(i=1;i<=n;i++)
	  for(j=1;j<=n;j++)
	    a[i][j]=1e9;
	for(i=1;i<=m;i++){
		scanf("%lld%lld%lld",&x,&y,&z);
		a[x][y]=z;
	}
	for(i=1;i<=n;i++)  f[i]=1e9;
	f[qi]=0;v[qi]=1;
	cf=x;
	for(i=1;i<=n-1;i++){
		for(j=1;j<=n;j++)
		  if(v[j]==0&&f[j]>f[cf]+a[cf][j])  f[j]=f[cf]+a[cf][j];
		mi=1e9;
		for(j=1;j<=n;j++)
		  if(v[j]==0&&f[j]<mi)  mi=f[j],cf=j;
		v[cf]=1;
	}
	for(i=1;i<=n;i++)  printf("%lld ",f[i]);
}

回复

共 8 条回复，欢迎继续交流。

正在加载回复...