Dijkstra TLE #1 & #6 求助

P4779 【模板】单源最短路径（标准版）

Gcc_Gdb_7_8_1 @ 2024-10-30 21:46:44

Code:

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

#define LL long long
#define Pii pair<int, int>

namespace gdb7
{
    struct Edge {
        int w, to, nxt;
    } edges[500010];
    int head[100010], eid, dis[100010], vis[100010], n, m, s;
    inline void insert(int u, int v, int w) {
        edges[++eid].w = w;
        edges[eid].to = v;
        edges[eid].nxt = head[u];
        head[u] = eid;
    }
    struct Node {
        int w, u;
        inline const bool operator<(const Node &rhs) const {
            return w < rhs.w;
        }
    };
    priority_queue<Node> pq;
    void dijkstra(int s) {
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; ++i) {
            dis[i] = 2147483647;
        }
        dis[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            Node tmp = pq.top();
            vis[tmp.u] = 1;
            pq.pop();
            for (int i(head[tmp.u]); ~i; i = edges[i].nxt) {
                if (dis[edges[i].to] > dis[tmp.u] + edges[i].w) {
                    dis[edges[i].to] = dis[tmp.u] + edges[i].w;
                    pq.push({tmp.w + edges[i].w, edges[i].to});
                }
            }
        }
    }
    int main() {
        memset(head, -1, sizeof(head));
        scanf("%d%d%d", &n, &m, &s);
        for (int i = 1; i <= m; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            insert(u, v, w);
        }
        dijkstra(s);
        for (int i = 1; i <= n; ++i) {
            printf("%d%c", dis[i], " \n"[i == n]);
        }
        return 0;
    }
};

int main()
{
    return gdb7::main();
}

弱化版 AC，标准版 TLE #1 & #6。

by qazsedcrfvgyhnujijn @ 2024-10-30 21:54:41

这不是相当于 vis 白开了？
vis[tmp.u] = 1; 前面加一句 if (vis[tmp.u]) continue;

by Gcc_Gdb_7_8_1 @ 2024-10-30 21:57:11

@qazsedcrfvgyhnujijn 然鹅成了 16 pts

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

#define LL long long
#define Pii pair<int, int>

namespace gdb7
{
    struct Edge {
        int w, to, nxt;
    } edges[500010];
    int head[100010], eid, dis[100010], vis[100010], n, m, s;
    inline void insert(int u, int v, int w) {
        edges[++eid].w = w;
        edges[eid].to = v;
        edges[eid].nxt = head[u];
        head[u] = eid;
    }
    struct Node {
        int w, u;
        inline const bool operator<(const Node &rhs) const {
            return w < rhs.w;
        }
    };
    priority_queue<Node> pq;
    void dijkstra(int s) {
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; ++i) {
            dis[i] = 2147483647;
        }
        dis[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            Node tmp = pq.top();
            if (vis[tmp.u]) {
                continue;
            }
            vis[tmp.u] = 1;
            pq.pop();
            for (int i(head[tmp.u]); ~i; i = edges[i].nxt) {
                if (dis[edges[i].to] > dis[tmp.u] + edges[i].w) {
                    dis[edges[i].to] = dis[tmp.u] + edges[i].w;
                    pq.push({tmp.w + edges[i].w, edges[i].to});
                }
            }
        }
    }
    int main() {
        memset(head, -1, sizeof(head));
        scanf("%d%d%d", &n, &m, &s);
        for (int i = 1; i <= m; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            insert(u, v, w);
        }
        dijkstra(s);
        for (int i = 1; i <= n; ++i) {
            printf("%d%c", dis[i], " \n"[i == n]);
        }
        return 0;
    }
};

int main()
{
    return gdb7::main();
}

by wbc1030 @ 2024-10-30 23:10:57

@Gcc_Gdb_7_8_1 您把那个pq.push(tmp.w....)放入一个if(!vis[edges[i].to){}里面,if{}里面再加一个vis[edges[i].to]=1;,,,,再把您那个vis[tmp.u]=1改为0；

by harrycy123 @ 2024-10-31 18:12:12

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

#define LL long long
#define Pii pair<int, int>

namespace gdb7
{
    struct Edge {
        int w, to, nxt;
    } edges[500010];
    int head[100010], eid, dis[100010], vis[100010], n, m, s;
    inline void insert(int u, int v, int w) {
        edges[++eid].w = w;
        edges[eid].to = v;
        edges[eid].nxt = head[u];
        head[u] = eid;
    }
    struct Node {
        int w, u;
        inline const bool operator<(const Node &rhs) const {
            return rhs.w < w;
        }
    };
    priority_queue<Node> pq;
    void dijkstra(int s) {
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; ++i) {
            dis[i] = 2147483647;
        }
        dis[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            Node tmp = pq.top();
            pq.pop();
            if(vis[tmp.u]) continue;
            vis[tmp.u] = 1;
            for (int i=head[tmp.u]; ~i; i = edges[i].nxt) {
                if (dis[edges[i].to] > dis[tmp.u] + edges[i].w) {
                    dis[edges[i].to] = dis[tmp.u] + edges[i].w;
                    if(!vis[edges[i].to])pq.push({dis[edges[i].to], edges[i].to});
                }
            }
        }
    }
    int main() {
        memset(head, -1, sizeof(head));
        scanf("%lld%lld%lld", &n, &m, &s);
        for (int i = 1; i <= m; ++i) {
            int u, v, w;
            scanf("%lld%lld%lld", &u, &v, &w);
            insert(u, v, w);
        }
        s=1;
        dijkstra(s);
        for (int i = 1; i <= n; ++i) {
            printf("%lld%c", dis[i], " \n"[i == n]);
        }
        return 0;
    }
};

signed main()
{
    return gdb7::main();
}

node里面比较写反了然后vis要用上，就过了提交记录