社区讨论

各位大佬,用狄做的,为什么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 条回复,欢迎继续交流。

正在加载回复...