求救?

wuhaoran2012 @ 2023-09-09 11:58:53

#import<bits/stdc++.h>
using namespace std;
inline int read (){int x;cin>>x;return x;}
struct node {
    int to,dis;
    bool operator< (const node &x) const {
        return dis < x.dis;
    }
};
int n,m,s;
vector<node> a[(int)1e5+10];
int dis[(int)1e5+10];
bool vis[(int)1e5+10];
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++) a[read()].push_back({read(),read()});
    fill(dis+1,dis+n+1,INT_MAX);
    dis[s]=0;
    priority_queue<node>q;
    q.push({s,0});
    while(!q.empty()){
        auto [u,d] = q.top();
        q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(auto j: a[u] ){
            auto [to,d] = j;
            if(dis[to] > dis[u] + d) {
                dis[to] = dis[u] +d;
                q.push({to,dis[to]});
            }
        }
    }
    for(int i=1;i<=n;i++) {
        cout<<dis[i]<<" \n"[i==n];
    }
    return 0;
}

by SJZ2010 @ 2023-09-09 12:48:43

优先队列运算符要反着重载吧

by SJZ2010 @ 2023-09-09 12:50:28

@wuhaoran2012

by SJZ2010 @ 2023-09-09 12:54:06

这样

#import<bits/stdc++.h>
using namespace std;
inline int read (){int x;cin>>x;return x;}
struct node {
    int to,dis;
    bool operator< (const node &x) const {
        return dis > x.dis;//改下这里
    }
};
int n,m,s;
vector<node> a[(int)1e5+10];
int dis[(int)1e5+10];
bool vis[(int)1e5+10];
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++) a[read()].push_back({read(),read()});
    fill(dis+1,dis+n+1,INT_MAX);
    dis[s]=0;
    priority_queue<node>q;
    q.push({s,0});
    while(!q.empty()){
        auto [u,d] = q.top();
        q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(auto j: a[u] ){
            auto [to,d] = j;
            if(dis[to] > dis[u] + d) {
                dis[to] = dis[u] +d;
                q.push({to,dis[to]});
            }
        }
    }
    for(int i=1;i<=n;i++) {
        cout<<dis[i]<<" \n"[i==n];
    }
    return 0;
}