前三个点TLE,求大佬指点

P1342 请柬

cjh88939492 @ 2023-03-09 11:46:18

求大佬指点

#include<iostream> 
#include<cstdio> 
#include<string>
#include<cmath>
#include<cstring>
#include <algorithm>
#include<iomanip>
#include<queue>
#include<limits.h>
#define INF 1<<30;
using namespace std;
const long long u = 2000005;

int n, m, p;
long long dis1[u],dis2[u];
bool vis1[u], vis2[u];
int head1[u], head2[u], cnt1 = 1, cnt2 = 1;

struct node {
    long long dis;
    int pos;
    bool operator<(const node& x)const {
        return x.dis < dis;
    }
};

struct edge {
    int to;
    int w;
    int next;
}edge1[u], edge2[u];

inline void addedge1(int u, int v, long long z) {
    edge1[cnt1].to = v;
    edge1[cnt1].w = z;
    edge1[cnt1].next = head1[u];
    head1[u] = cnt1++;
}

inline void addedge2(int u, int v, long long z) {
    edge2[cnt2].to = v;
    edge2[cnt2].w = z;
    edge2[cnt2].next = head2[u];
    head2[u] = cnt2++;
}

inline void dijkstra1(int num) {
    priority_queue<node> q;
    memset(vis1, 0, sizeof(vis1));
    memset(dis1, 0x3f, sizeof(dis1));
    dis1[num] = 0;
    q.push(node{ 0,num });
    while (!q.empty()) {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if (vis1[x]) {
            continue;
        }
        vis1[x] = 1;
        for (int i = head1[x]; i; i = edge1[i].next) {
            int y = edge1[i].to;
            if (dis1[y] > dis1[x] + edge1[i].w) {
                dis1[y] = dis1[x] + edge1[i].w;
            }
            if (!vis1[y]) {
                q.push(node{ dis1[y],y });
            }
        }
    }
}

inline void dijkstra2(int num) {
    priority_queue<node> q;
    memset(vis2, 0, sizeof(vis2));
    memset(dis2, 0x3f, sizeof(dis2));
    dis2[num] = 0;
    q.push(node{ 0,num });
    while (!q.empty()) {
        node tmp = q.top();
        q.pop();
        int x = tmp.pos, d = tmp.dis;
        if (vis2[x]) {
            continue;
        }
        vis2[x] = 1;
        for (int i = head2[x]; i; i = edge2[i].next) {
            int y = edge2[i].to;
            if (dis2[y] > dis2[x] + edge2[i].w) {
                dis2[y] = dis2[x] + edge2[i].w;
            }
            if (!vis2[y]) {
                q.push(node{ dis2[y],y });
            }
        }
    }
}

int main() {
    cin>>n>>m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin>>a>>b>>c;
        addedge1(a, b, c);
        addedge2(b, a, c);
    }
    dijkstra1(1);
    dijkstra2(1);
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += dis1[i] + dis2[i];
    }
    cout << ans;
    return 0;
}

by KinoTsuki @ 2023-10-08 19:48:08

快读+ O2 @cjh88939492


by Lele_Programmer @ 2024-01-26 14:43:43

dij + 堆优化


|