优先队列优化，可是好像走完一次循环就输出了，不知咋回事

MC_OIer @ 2023-11-04 14:48:08

#include<bits/stdc++.h>
using namespace std;
struct node{
    int to,w;
    bool operator<(const node&a)const{
        w>a.w;
    }
};
priority_queue<node>q;
vector<node>a[10005];
int dist[10005],n,m,s;
int flag[10005];
int main(){
    memset(dist,0x7f,sizeof dist);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        a[x].push_back(node{y,z});
    }
    dist[s]=0;
    q.push(node{s,0});
    for(int i=1;i<=n;i++){
        q.push(node{i,2147483647});
    }
    for(int i=1;i<=n;i++){
        qushu:;
        int tot=q.top().to;
        q.pop();
        if(flag[tot])goto qushu;
        flag[tot]=1;
        for(int j=0;j<a[tot].size();j++){
            if(dist[a[tot][j].to]>dist[tot]+a[tot][j].w){
                dist[a[tot][j].to]=dist[tot]+a[tot][j].w;
            }
            q.push(node{a[tot][j].to,dist[a[tot][j].to]});
        }
    }
    for(int i=1;i<=n;i++)cout<<dist[i]<<' ';
    return 0;
}

by atarashiTLE @ 2023-11-04 14:56:19

    bool operator<(const node&a)const{
        w>a.w;
    }

好活

by MC_OIer @ 2023-11-04 15:06:26

#include<bits/stdc++.h>
using namespace std;
struct node{
    int to,w;
    bool operator<(const node&a)const{
        w<a.w;
    }
};
priority_queue<node>q;
vector<node>a[200005];
int dist[200005],n,m,s;
int flag[200005];
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        a[x].push_back(node{y,z});
    }
    for(int i=1;i<=n;i++){
        dist[i]=1e10;
    }
    dist[s]=0;
    q.push(node{s,0});
    for(int i=1;i<=n;i++){
        qushu:;
        int tot=q.top().to;
        q.pop();
        if(!flag[tot]){
            flag[tot]=1;
            for(int j=0;j<a[tot].size();j++){
                if(dist[a[tot][j].to]>dist[tot]+a[tot][j].w){
                    dist[a[tot][j].to]=dist[tot]+a[tot][j].w;
                    if(!flag[a[tot][j].to])
                        q.push(node{a[tot][j].to,dist[a[tot][j].to]});
                }

            }
        }
    }
    for(int i=1;i<=n;i++)cout<<dist[i]<<' ';
    return 0;
}

改了一下，但还是只能过一个点啊啊啊

by MC_OIer @ 2023-11-04 15:08:39

@atarashiTLE 帮我看看哪里错了(@.@)

by MC_OIer @ 2023-11-04 16:02:00

WA on #1#2#3#4#6

by MC_OIer @ 2023-11-08 17:37:36

A辽，此帖结