dij堆优化re求助

P4779 【模板】单源最短路径(标准版)

KANO07 @ 2023-11-16 16:08:59

#include<bits/stdc++.h>
using namespace std;
int n;
int start; 
//邻节点 
struct adjNode{
    int index;
    int val;//此处val是边长
    adjNode *next;
};
//头结点 
struct headNode{
    int val;
    adjNode* first;
};
//图 
struct Gragh{
    headNode head[int(1e4+1)];
};

//连接边 
void insertedge(Gragh &G,int i,int j,int value){
    adjNode *tmp;
    tmp = new adjNode;
    tmp->index = j;
    tmp->val = value;
    tmp->next = G.head[i].first;
    G.head[i].first = tmp;
}

//构造邻接表 
void creat(Gragh &G){
    int m;
    cin>>n>>m>>start;
    //初始化头结点 
    for(int i = 1;i<=n;i++){
        G.head[i].val = i;
        G.head[i].first = nullptr;
    }
    for(int i = 1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        insertedge(G,u,v,w);
    }
}

//优先队列节点 
struct minNode{
    long long v;
    long long index;

    bool operator< (const minNode &t)const
    {
        return t.v<v;
    }
};

vector<long long>dij(Gragh& G,int root){
    priority_queue<minNode>que;
    //distance[i]原点到i的距离 
    vector<long long>dis(n+1,INT_MAX);
    dis[root] = 0;
    que.push({0,root});
    while(!que.empty())
    { 
        minNode cur = que.top();
        que.pop();
        if(dis[cur.index]<cur.v) continue;

        //更新相邻点
        adjNode* i = G.head[cur.index].first;
        while(i!=nullptr){
            if(dis[i->index] > dis[cur.index]+i->val){
                dis[i->index] = dis[cur.index]+i->val;
                que.push({dis[i->index],i->index});
            }
            i=i->next;
        }
    }
    return dis;
}

int main(){
    Gragh G;
    creat(G);
    vector<long long>ans = dij(G,start);
    //遍历输出 
    for(long long i = 1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
} 

by Bodhi @ 2023-11-16 16:14:21

headNode数组开小了吧,数据范围给的是n<=1e5


by KANO07 @ 2023-11-16 17:24:57

@Bodhi 感谢感谢orz


|