0tps,求助！

corner_xiejunqi @ 2024-12-08 12:22:14

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,s;
vector<pair<int,int> > g[N];
int dis[N],book[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
signed main(){
    // step 1、读题、声明变量
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(false);
    // step 2、输入
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v,w));
    }
    // step 3、处理
    for(int i=1;i<=n;i++) dis[i]=2147483647;
    dis[s]=0;
    for(int i=0;i<g[s].size();i++){
        dis[g[s][i].first]=min(g[s][i].second,dis[g[s][i].first]);
    }
    q.push(make_pair(0,s));
    while(!q.empty()){
        pair<int,int> now=q.top();
        cout<<q.top().second<<' '<<q.top().first<<'\n';
        q.pop();
        int x=now.second,y=now.first;
        if(book[x]) continue;
        book[x]=1;
        for(int i=0;i<g[x].size();i++){
            int to=g[x][i].first,val=g[x][i].second;
            if(dis[to]>dis[x]+val){
                dis[to]=dis[x]+val;
                if(!book[to]) q.push(make_pair(val,to));
            }
        }
    }
    // step 4、输出
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<' ';
    }
    return 0;
}

by corner_xiejunqi @ 2024-12-08 12:28:11

改了一下，54pts,求助！

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,s;
vector<pair<int,int> > g[N];
int dis[N],book[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
signed main(){
    // step 1、读题、声明变量
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(false);
    // step 2、输入
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back(make_pair(v,w));
    }
    // step 3、处理
    for(int i=1;i<=n;i++) dis[i]=2147483647;
    dis[s]=0;
    for(int i=0;i<g[s].size();i++){
        dis[g[s][i].first]=min(g[s][i].second,dis[g[s][i].first]);
    }
    q.push(make_pair(0,s));
    for(int i=1;i<=n;i++){
        q.push(make_pair(dis[i],i));
    }
    book[s]=1;
    while(!q.empty()){
        pair<int,int> now=q.top();
        //cout<<"1:"<<q.top().second<<' '<<q.top().first<<'\n';
        q.pop();
        int x=now.second,y=now.first;
        if(book[x]) continue;
        book[x]=1;
        for(int i=0;i<g[x].size();i++){
            int to=g[x][i].first,val=g[x][i].second;
            //cout<<"2:"<<to<<' '<<val<<'\n';
            if(dis[to]>dis[x]+val){
                dis[to]=dis[x]+val;
                if(!book[to]) q.push(make_pair(val,to));
            }
        }
    }
    // step 4、输出
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<' ';
    }
    return 0;
}