社区讨论
求助大佬
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 条回复,欢迎继续交流。
正在加载回复...