dijkstra堆优化16'求调（玄关

原来能得64pts，改完就成16pts，怪邪乎的

#include<bits/stdc++.h>

using namespace std;

const int maxN = 1e5 + 10, maxM = 2e5 + 10, INF = 2147483647;
int n, m, start;
struct Edge {
    int v, w, next;
} e[maxM];
int head[maxN], cnt;

void add_edge(int u, int v, int w) {
    e[++cnt] = {v, w, head[u]}, head[u] = cnt;
}

struct node {
    int dist, pos;
    bool operator>(const node &p) const{
        return dist > p.dist;
    }
    node() : dist(0), pos(0) {  }
    node(int d, int p) { this->dist = d, this->pos = p; }
};

int dis[maxN];
bool vis[maxN];

priority_queue<node, vector<node>, greater<node>> q;
void dijkstra() { //O(nlogn)
    fill(dis, dis+n+1, INF);
    dis[start] = 0;
    q.emplace(node{-dis[start], start});

    while(!q.empty()) {
        int u = q.top().pos; q.pop();

        if(!vis[u]) {
            vis[u] = true;

            for(int j=head[u]; j; j=e[j].next)
                if(dis[e[j].v]>dis[u]+e[j].w) {
                    dis[e[j].v] = dis[u] + e[j].w;
                    if(!vis[e[j].v])
                        q.emplace(node{-dis[e[j].v], e[j].v});
                }
        }
    }
} 

int main() { //P4779 【模板】单源最短路径（标准版）
    ios::sync_with_stdio(false);
    cin.tie(), cout.tie();

    cin >> n >> m >> start;
    int u, v, w;
    while(m--) cin >> u >> v >> w, add_edge(u, v, w);

    dijkstra();

    for(int i=1; i<=n; i++) cout << dis[i] << ' ';
    cout << endl; 

    return 0;
}

/*
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

0 2 4 3
*/