求助，10pts，tle+wa


1


原题

我的10pts wa+tle die码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100002, M = 500002;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll h[N], e[M], ne[M], w[M], idx, state[N], dist[N], ene[N], n, m, ans;
void add(ll a, ll b, ll c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = ++ idx;
}
void dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    dist[n] = 0;
    for (int i = h[n]; i != -1; i = ne[i]) dist[i] = w[i];
    for (int i = 1; i <= n; i ++ ) {
        int t = -1;
        for (int j = 1; j <= n; j ++ ) if (!state[j] && (t == -1 || dist[j] < dist[t])) t = j;
        state[t] = 1;
        for (int j = h[t]; j != -1; j = ne[j]) {
            int i = e[j];
            if (dist[i] == INF) dist[i] = w[j];
            else dist[i] = min(dist[i], dist[t] + w[j]);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) h[i] = -1, scanf("%lld", &ene[i]);
    while (m -- ) {
        ll a, b, w;
        scanf("%lld%lld%lld", &a, &b, &w);
        add(a, b, w);        
        add(b, a, w);
    }
    dijkstra();
    for (int i = 1; i <= n; i ++ ) if (dist[i] <= dist[1]) ans += ene[i];
    cout << ans;
}


提问于8天前
7860


1 个问答


2

你看看有什么区别

注意别爆$int$，要开$longlong$

#include <bits/stdc++.h>
using namespace std;
const long long N = 100010, M = 1000010;
long long head[N], ver[M], edge[M], nxt[M];
long long d[N], robot[N], ans;
bool st[N];
long long n, m, tot;
priority_queue< pair<long long, long long> > q;
void add(long long x, long long y, long long z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void dijkstra() {
    memset(d, 0x7f, sizeof d);
    memset(st, 0, sizeof st);
    d[n] = 0;
    q.push(make_pair(0, n));
    while (q.size()) {
        long long x = q.top().second; q.pop();
        if (st[x]) continue;
        st[x] = 1;
        for (long long i = head[x]; i; i = nxt[i]) {
            long long y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                q.push(make_pair(-d[y], y));
            }
        }
    }
}
int main() {
    scanf("%lld%lld", &n, &m);
    for (long long i = 1; i <= n; i++) scanf("%lld", &robot[i]);
    for (long long i = 1; i <= m; i++) {
        long long x, y, z;
        scanf("%lld%lld%lld", &x, &y, &z);
        add(x, y, z); add(y, x, z);
    }
    dijkstra();
    // for (long long i = 1; i <= n; i++) printf("%lld ", d[i]); puts("");
    for (long long i = 1; i <= n; i++)
        if (d[i] <= d[1]) ans += robot[i];
    printf("%lld", ans);
    return 0;
}
回答于7天前
113632
我来回答