样例过不了求助（玄关）

ycy1124 @ 2024-06-27 08:17:53

#include<bits/stdc++.h>
using namespace std;
int ans[100001];
bool bj[100001];
int n,m,q,tot=0;
struct Node{
    int to,w;   
};
Node b[100001];
vector <Node> a[100001];
void work(int x){
    if(x/2>=1&&b[x].w<b[x/2].w){
        swap(b[x].w,b[x/2].w);
        work(x/2);
    }
}
void work1(int x){
    if(b[x*2].w<b[x*2+1].w&&x*2+1<=tot&&b[x*2].w<b[x].w){
        swap(b[x*2].w,b[x].w);
        work1(x*2);
    }
    else if(x*2+1<=tot&&b[x*2+1].w<b[x].w){
        swap(b[x*2+1],b[x]);
        work1(x*2+1);
    }
    else if(x*2+1>tot&&x*2<=tot&&b[x*2].w<b[x].w){
        swap(b[x*2],b[x]);
        work1(x*2);
    }
    else{
        return;
    }
}
void bfs(int i,int js){
    if(bj[i]){
        return;
    }
    bj[i]=1;
    ans[i]=js;
    bj[i]=1;
    for(auto it:a[i]){
        if(!bj[it.to]){
            b[++tot].w=it.w+js;
            b[tot].to=it.to;
            work(tot); 
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        a[u].push_back({v,w});
    }
    b[++tot]={q,0};
    while(tot!=0){
        bfs(b[1].to,b[1].w);
        swap(b[1],b[tot]);
        tot--;
        work1(1);
    }
    for(int i=1;i<=n;i++){
        printf("%d ",ans[i]);
    }
    return 0;
}

by ycy1124 @ 2024-06-27 09:22:08

@WJX120423

我人麻了，好像都不会

by ycy1124 @ 2024-06-27 09:22:35

只能重构了吗QwQ

by Miracle_1024 @ 2024-06-27 09:22:54

@ycy1124

优先队列也不难，看一下就会了

by WJX120423 @ 2024-06-27 09:25:50

@ycy1124 应该是的

by ycy1124 @ 2024-06-27 09:26:19

@WJX120423

QwQ

by WJX120423 @ 2024-06-27 09:30:16

@ycy1124 加油吧

by ycy1124 @ 2024-06-27 09:32:09

@WJX120423 @Miracle_1024

我在原代码上改出来了

by ycy1124 @ 2024-06-27 09:32:57

@WJX120423 @Miracle_1024

有没有可能我写堆的时候只将w交换

by ycy1124 @ 2024-06-27 09:33:24

#include<bits/stdc++.h>
using namespace std;
int ans[100001];
bool bj[100001];
int n,m,q,tot=0;
struct Node{
    int to,w;   
};
Node b[100001];
vector <Node> a[100001];
void work(int x){
    if(x/2>=1&&b[x].w<b[x/2].w){
        swap(b[x],b[x/2]);
        work(x/2);
    }
}
void work1(int x){
    if(b[x*2].w<b[x*2+1].w&&x*2+1<=tot&&b[x*2].w<b[x].w){
        swap(b[x*2],b[x]);
        work1(x*2);
    }
    else if(x*2+1<=tot&&b[x*2+1].w<b[x].w){
        swap(b[x*2+1],b[x]);
        work1(x*2+1);
    }
    else if(x*2+1>tot&&x*2<=tot&&b[x*2].w<b[x].w){
        swap(b[x*2],b[x]);
        work1(x*2);
    }
    else{
        return;
    }
}
void bfs(int i,int js){
    //printf("%d %d\n",i,js);
    if(bj[i]){
        return;
    }
    bj[i]=1;
    ans[i]=js;
    for(auto it:a[i]){
        if(!bj[it.to]){
            b[++tot].w=it.w+js;
            b[tot].to=it.to;
            work(tot); 
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        a[u].push_back({v,w});
    }
    b[++tot]={q,0};
    while(tot!=0){
        bfs(b[1].to,b[1].w);
        swap(b[1],b[tot]);
        tot--;
        work1(1);
    }
    for(int i=1;i<=n;i++){
        printf("%d ",ans[i]);
    }
    return 0;
}

by WJX120423 @ 2024-06-27 09:51:59

@ycy1124 emm 是我太菜了吧，还是看不懂QwQ