guer_loser_lcz @ 2024-07-09 19:06:13

#include<bits/stdc++.h>
using namespace std;
long long n,m,s,mn[100100];
struct note{
    long long to,w;
};
vector<note> e[200100];
bool vis[100100];
void dij(int x){
    priority_queue<int> q;
    q.push(x);
    while(!q.empty()){
        int k=q.top();
        q.pop();
        if(vis[k])continue;
        vis[k]=1;
        for(int i=0;i<e[k].size();i++){
            if(mn[e[k][i].to]>mn[k]+e[k][i].w){
                mn[e[k][i].to]=mn[k]+e[k][i].w;
                if(!vis[e[k][i].to]){
                    q.push(e[k][i].to);
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1,x,y,z;i<=m;i++){
        cin>>x>>y>>z;
        e[x].push_back({y,z});
    }
    for(int i=2;i<=n;i++)mn[i]=1e10;
    dij(1);
    for(int i=1;i<=n;i++)cout<<mn[i]<<" ";
    return 0;
}

by Mr_RedStone @ 2024-07-10 21:42:01

额 优先队列的类型应该是一个结构体，包含当前点与当前算出的最短路长度，例如。

struct Node{
  int x,d;//x当前点，d距离
  friend bool operator <(Node a,Node b){
    return a.d>b.d;//优先队列满足条件的放后面
  }
}
...
priority_queue<Node> q

优先队列根据距离排序，并非点编号。

孩子你无敌了 :D。

by Mr_RedStone @ 2024-07-10 21:44:50

@lczcy1 给你改了亿下

#include<bits/stdc++.h>
using namespace std;
long long n,m,s,mn[100100];
struct note{
    long long to,w;
};
struct Node{
    int x,d;
    friend bool operator <(Node a,Node b){
        return a.d>b.d;
    }
};
vector<note> e[200100];
bool vis[100100];
void dij(int x){
    priority_queue<Node> q;
    q.push({x,0});
    while(!q.empty()){
        auto [k,d]=q.top();
        q.pop();
        if(vis[k])continue;
        vis[k]=1;
        for(int i=0;i<e[k].size();i++){
            if(mn[e[k][i].to]>mn[k]+e[k][i].w){
                mn[e[k][i].to]=mn[k]+e[k][i].w;
                if(!vis[e[k][i].to]){
                    q.push({e[k][i].to,mn[e[k][i].to]});
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1,x,y,z;i<=m;i++){
        cin>>x>>y>>z;
        e[x].push_back({y,z});
    }
    for(int i=2;i<=n;i++)mn[i]=1e10;
    dij(1);
    for(int i=1;i<=n;i++)cout<<mn[i]<<" ";
    return 0;
}

by guer_loser_lcz @ 2024-07-10 21:53:43

@Mr_RedStone 严重怀疑这是你的代码

by guer_loser_lcz @ 2024-07-10 21:54:24

但又是我的

by Mr_RedStone @ 2024-07-11 08:34:39

@lczcy1 不是哥们[doge