社区讨论
各位大佬,用狄做的,为什么wa几个点啊
P3371【模板】单源最短路径(弱化版)参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo8dxjz9
- 此快照首次捕获于
- 2023/10/27 17:02 2 年前
- 此快照最后确认于
- 2023/10/27 17:02 2 年前
CPP
#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int maxw=2e31-1;
int n,m,s;
struct code{
int to,w;
};
queue<code> a[10001];
queue<int> p;
void work(int x,int dis[],bool b[])
{
code k;
bool t[n+1]={0};
while(!a[x].empty()){
k=a[x].front();a[x].pop();
if(b[k.to]) continue;
if(!t[k.to]){
p.push(k.to);t[k.to]=1;
}
dis[k.to]=min(dis[k.to],dis[x]+k.w);
}
b[x]=1;
if(p.empty()) return;
int v=p.front();p.pop();
work(v,dis,b);
}
int main()
{
cin>>n>>m>>s;
int dis[n+1],i,r;
bool b[n+1]={0};
code k;
for(i=1;i<=n;i++) dis[i]=maxw;
dis[s]=0;
for(i=0;i<m;i++){
cin>>r>>k.to>>k.w;
if(r==k.to) continue;
a[r].push(k);
}
work(s,dis,b);
for(i=1;i<=n;i++) cout<<dis[i]<<" ";
cin>>n;
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...