vector存边，36分求调

cxlian25 @ 2023-01-06 21:39:24

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int n,m,s,d[N],vis[N];
struct E{
    int to,dis;
};
vector<E>edge[N];
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int from,to,w;
        scanf("%d%d%d",&from,&to,&w);
        edge[from].push_back({to,w});
    }
    for(int i=1;i<=n;i++){
        if(i==s)d[i]=0;
        else d[i]=0x7fffffff;
    }
    priority_queue<int,vector<int>,greater<int>>q;
    q.push(s);
    while(!q.empty()){
        int x=q.top();q.pop();
        if(vis[x])
            continue;
        vis[x]=1;
        for(int i=0;i<edge[x].size();i++){
            if(d[edge[x][i].to]>d[x]+edge[x][i].dis){
                d[edge[x][i].to]=d[x]+edge[x][i].dis;
                if(!vis[edge[x][i].to])q.push(edge[x][i].to);
            }
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d ",d[i]);
    return 0;
}

by Kevin_Mamba @ 2023-01-06 21:51:31

@cxlian25 dij 好像不是按点编号排序吧，是按 dis。

by Kevin_Mamba @ 2023-01-06 21:53:36

@cxlian25

改一下以下这些地方。

struct E{
    int to,dis;
    inline bool operator < (const E &a) const
    {
        return dis>a.dis;
    }
};

    priority_queue<E>q;
    q.push({s,0});

        int x=q.top().to;q.pop();    

        if(!vis[edge[x][i].to])q.push({edge[x][i].to,d[edge[x][i].to]});

by Kevin_Mamba @ 2023-01-06 21:55:16

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int n,m,s,d[N],vis[N];
struct E{
    int to,dis;
    inline bool operator < (const E &a) const
    {
        return dis>a.dis;
    }
};
vector<E>edge[N];
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int from,to,w;
        scanf("%d%d%d",&from,&to,&w);
        edge[from].push_back({to,w});
    }
    for(int i=1;i<=n;i++){
        if(i==s)d[i]=0;
        else d[i]=0x7fffffff;
    }
    priority_queue<E>q;
    q.push({s,0});
    while(!q.empty()){
        int x=q.top().to;q.pop();
        if(vis[x])
            continue;
        vis[x]=1;
        for(int i=0;i<edge[x].size();i++){
            if(d[edge[x][i].to]>d[x]+edge[x][i].dis){
                d[edge[x][i].to]=d[x]+edge[x][i].dis;
                if(!vis[edge[x][i].to])q.push({edge[x][i].to,d[edge[x][i].to]});
            }
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d ",d[i]);
    return 0;
}

by cxlian25 @ 2023-01-06 22:04:13

@2124Kobe 多谢指点迷津，好人一生平安

by Kevin_Mamba @ 2023-01-06 22:05:31

@cxlian25 感谢祝福。