莫名re,4号关注回报
查看原帖
莫名re,4号关注回报
347589
Zelotz楼主2021/8/5 20:04

数组都开到1e7了 实在看不出来惹,求帮助

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define reg register int
#define msz(a) memset(a, 0, sizeof a);
typedef long long LL;
typedef pair <int, int> PII;
const int INF1 = 0x3f3f3f3f, INF2 = 0x7fffffff;
const int N = 1e7 + 5;
int n, h, tot, dis[N];
bool vis[N];
vector <PII> E[N];
bool spfa(int src) {
    for (int i = 1; i <= n; ++i) dis[i] = -INF1;
    queue <int> Q;
    Q.push(src);
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();
        // if (vis[x]) continue;
        vis[x] = 0;
        for (int i = 0; i < E[x].size(); ++i) {
            int a = E[x][i].first, b = E[x][i].second;
            if (dis[a] < dis[x] + b) {
                dis[a] = dis[x] + b;
                if (!vis[a]) Q.push(a), vis[a] = 1;
            }
        }
    }
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &h);
        for (int i = 1; i <= h; ++i) {
            int b, e, t;
            scanf("%d%d%d", &b, &e, &t);
            n = max(n, e);
            E[b - 1].push_back(mp(e, t));
        }
        for (int i = 1; i <= n; ++i) 
            E[i - 1].push_back(mp(i, 0)), E[i].push_back(mp(i - 1, -1));
        spfa(0);
        printf("%d\n", dis[n]);
        for (int i = 1; i <= n; ++i) if (!E[i].empty()) E[i].clear();
        msz(vis); msz(dis); n = 0;
        if (T) puts("");
    }
    return 0;
}
2021/8/5 20:04
加载中...