为什么我的答案很离谱

P1342 请柬

Light_LE @ 2024-10-05 18:20:08

跑样例结果输出超级大

#include <bits/stdc++.h>
#define maxn 1000003
using namespace std;
struct Edge {
    int v, w, next;
}edge1[maxn], edge2[maxn];
struct Data {
    long long dis; int pos;
    bool operator < (const Data &x) const {
        return x.dis < dis;
    }
};
int n, m, cnt1, cnt2, vis[maxn], head1[maxn], head2[maxn];
long long dis[maxn], ans;
priority_queue<Data> q;
void add1(int u, int v, int w) {
    cnt1++;
    edge1[cnt1].v = v;
    edge1[cnt1].w = w;
    edge1[cnt1].next = head1[u];
    head1[u] = cnt1;
}
void add2(int u, int v, int w) {
    cnt2++;
    edge2[cnt2].v = v;
    edge2[cnt2].w = w;
    edge2[cnt2].next = head2[u];
    head2[u] = cnt2;
}
void dijkstra(int start, Edge edge[], int head[]) {
    memset(dis, 0x7f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[start] = 0;
    q.push((Data){0, start});

    while (q.size()) {
        Data f = q.top(); q.pop();
        int pos = f.pos;

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

        for (int i = head[pos]; i; i = edge[i].next) {
            int v = edge[i].v, w = edge[i].w;
            if (dis[v] > dis[pos] + w) {
                dis[v] = dis[pos] + w;
                if (dis[v] == 0) {
                    q.push((Data){dis[v], v});
                }
            }
        }
    }
}
int main() {
    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add1(u, v, w);
        add2(v, u, w);
    }

    dijkstra(1, edge1, head1);

    for (int i = 1; i <= n; i++) {
        ans += dis[i];
    }

    // 初始化

    dijkstra(1, edge2, head2);

    for (int i = 1; i <= n; i++) {
        ans += dis[i];
    }

    cout << ans;
    return 0;
}

by Light_LE @ 2024-10-05 18:34:43

找到,应该把if (dis[v] == 0)改为if (vis[v] == 0)

我真是个小丑


|