蒟蒻求助,堆优化Dijkstra,TLE3个点

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

CodeZhangBorui @ 2023-06-29 21:12:50

rt,代码使用链式前向星存储,堆优化Dijkstra,但是仍然TLE3个点。提交记录。

同时,在本题的 弱化版 上不知为什么会 WA 一个点。提交记录

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#define INF 0x3f3f3f3f
#define N 100005
#define M 50*N
inline int read();
using namespace std;
int head[N], ver[M], edge[M], Next[M], n, m, tot;

void add(int x, int y, int z) {
    ver[++tot] = y;
    edge[tot] = z;
    Next[tot] = head[x];
    head[x] = tot;
}

priority_queue< pair<int, int> > Q;
bool vis[N];
int dist[N];
void dijkstra(int root) {
    memset(dist, 0x3f, sizeof dist);
    memset(vis, 0, sizeof vis);
    dist[root] = 0;
    Q.push(make_pair(0, root));
    while(!Q.empty()) {
        int x = Q.top().second;
        vis[x] = 1;
        Q.pop();
        for(int i = head[x]; ~i; i = Next[i]) {
            int t = ver[i];
            if(dist[t] > dist[x] + edge[i]) {
                dist[t] = dist[x] + edge[i];
                Q.push(make_pair(-dist[t], t));
            }
        }
    }
}

int main() {
    memset(head, -1, sizeof(head));
    tot = -1;
    int n, m, s;
    scanf("%d%d%d", &n, &m, &s);
    int x, y, z;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    dijkstra(s);
    for(int i = 1; i <= n; i++) {
        printf("%d ", dist[i]);
    }
    return 0;
}

inline int read() {
    int x = 0, f = 1;
    char ch;
    ch = getchar();
    while (ch > '9' || ch < '0') {
        if (ch == '-')
            f = -f;
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0') {
        x = (x << 1) + (x << 3) + (ch & 15);
        ch = getchar();
    }
    return x * f;
}

by sto_5k_orz @ 2023-06-29 21:21:38

@CodeZhangBorui 你是不是数组开太大了


by sto_5k_orz @ 2023-06-29 21:22:44

for(int i = head[x]; ~i; i = Next[i]) {

应该改为

for(int i = head[x]; i; i = Next[i]) {

by modinte @ 2023-06-29 21:23:20

@CodeZhangBorui 所以,你的 vis 有什么用?


by sto_5k_orz @ 2023-06-29 21:23:42

唉不对,我再看一下


by 滑不拉稽 @ 2023-06-29 21:23:45

少一句

if(vis[x]) continue;

by sto_5k_orz @ 2023-06-29 21:26:13

你应该加一句:

if(dist[x] != -q.top().second) continue;

by sto_5k_orz @ 2023-06-29 21:26:52

不然会 TLE,我试过了


by misaka2784 @ 2023-06-30 17:13:41

你的vis没用啊,看我的手写堆模板


by zzb1217 @ 2023-08-04 12:02:01

少了一句


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

|