爆零求助

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

jiqimaomaomao @ 2023-10-01 15:26:54

WA

#include <bits/stdc++.h>
#include <queue>
#include <math.h>
using namespace std;

struct EDGE
{
    int to;
    int next;
    int value;
};

struct NODE
{
    int pos, dis;

    bool operator< (const NODE x)const {
        return x.dis < dis;
    }
};

EDGE edge[200000];
int head[100000], cnt = 0, dist[100000], s;
bool vis[100000];
priority_queue <NODE> q;

void dijkstra ()
{
    NODE tmp;
    int p;

    q.push(NODE{s, 0});

    while (!q.empty()) {
        tmp = q.top();
        q.pop();
        p = tmp.pos;

        if (vis[p]) {
            continue;
        }
        vis[p] = 1;

        int y;
        for (int i = head[p]; i != 0; i = edge[i].next) {
            y = edge[i].to;
            if (dist[y] > dist[p] + edge[i].value) {
                dist[y] = dist[p] + edge[i].value;
            }
            if (!vis[y]) {
                q.push(NODE{y, dist[y]});
            }
        }

    }
}

int main ()
{
    int n, m, u, v, w;

    cin >> n >> m >> s;

    memset(dist, INFINITY, 100000);
    memset(vis, false, 100000);

    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;

        cnt++;
        edge[cnt].to = v;
        edge[cnt].next = head[u];
        head[u] = cnt;
        edge[cnt].value = w;
    }

    dist[s] = 0;

    dijkstra();

    for (int i = 1; i <= n; i++) {
        cout << dist[i] << " ";
    }

    return 0;
}

by jiqimaomaomao @ 2023-10-02 10:41:22

不开堆优化TLE,开了WA


by jiqimaomaomao @ 2023-10-08 18:10:11

ACed,本帖完


|