dij堆优化有3个MLE求助

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

gnailuyiab @ 2023-08-04 11:43:34

求求大佬帮忙看一下,找了很久没明白是哪里的问题

代码如下

#include<bits/stdc++.h>
using namespace std;
#define Vertex int
#define MaxWeight 1000000005

int dist[100005];
int visited[100005];
typedef struct node{
    int v;
    int w;
    node(int v_, int w_): v(v_), w(w_){}
} Node;

pair<int,int> p;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater< pair<int,int> > > Heap;
vector<Node> Graph[100005];

int main(){
    int n, m ,s;
    cin>>n>>m>>s;
    int u, v, w;
    for(int i = 0; i < m; i++){
        scanf("%d %d %d", &u, &v, &w);
        Graph[u].push_back(node(v,w));
    } //读入建立图

    //Dijkstra
    //初始化
    for(int i = 1; i <= n; i++){
        dist[i] = MaxWeight;
    }
    dist[s] = 0;
    Heap.push(make_pair(dist[s],s));

    while(!Heap.empty()){
        pair<int,int> org = Heap.top(); Heap.pop();
        Vertex minv = org.second;
        visited[minv] = 1;
        for(int i = 0; i < Graph[minv].size(); i++){
            Vertex adj = Graph[minv][i].v;
            int adjw = Graph[minv][i].w;
            if(!visited[adj]){
                dist[adj] = min(dist[adj], dist[minv]+adjw);
                Heap.push(make_pair(dist[adj], adj));
            }
        }
    }

    printf("%d", 0);
    for(int i = 2; i <= n; i++){
        printf(" %d", dist[i]);
    }
    return 0;
}

|