堆优化为什么也会TLE,T了3个点,不理解了

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

Dusk777 @ 2024-06-01 10:59:03

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

#define ll long long
const long long inf = 2147483647;

struct adjnode {
    ll goal;
    ll w;
};

int main() {
    ll n, m, s;
    cin >> n >> m >> s;

    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    vector<vector<adjnode>> adj(n + 1);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> heap;
    vector<ll> dist(n + 1, inf);
    vector<ll> vis(n + 1, 1);

    for (int i = 1; i <= m; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        adjnode tmp;
        tmp.goal = v;
        tmp.w = w;
        adj[u].push_back(tmp);
    }

    dist[s] = 0;
    vis[s] = 0;
    heap.push({0, s});

    while (!heap.empty()) {
        ll start = heap.top().second;
        heap.pop();

        for (int i = 0; i < adj[start].size(); i++) {
            adjnode next = adj[start][i];
            ll new_dist = dist[start] + next.w;
            if (new_dist < dist[next.goal]) {
                dist[next.goal] = new_dist;
                heap.push({dist[next.goal], next.goal});
            }
        }
    }

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

    return 0;
}

by DrAlfred @ 2024-06-01 11:22:36

@Dusk777 你的 Dijkstra 更新了一些无用的点。

每次拿出 start 之后要判断一下:


ll start = heap.top().second, w = heap.top().first;
heap.pop();
if (dis[start] != w) { 
    continue;
}

by Genius_Star @ 2024-06-01 11:22:52

您的 vis 数组是用来给谁看的?


by DrAlfred @ 2024-06-01 11:23:47

笔误,dist


by Dusk777 @ 2024-06-01 15:40:52

@DrAlfred 咱们的意思是如果从heap中拿出的点已经不是dist中的最短路了,就跳过本次循环吗,感谢,我似乎理解了


by Dusk777 @ 2024-06-01 15:43:07

@Genius_Star 抱歉,之前做弱化版时考虑的普通diji没有使用堆,采用vis标记已经访问过的节点,但是在这里不知道如何讨论vis数组,同时又忘记删去了,故混进无用的数据


|