P1119 灾后重建

七色丶人偶使 · 2020-12-15 07:34:02 · 个人记录

P1119 灾后重建

突然发现模拟赛考过这题。。。

大抵就是按时间更新，floyd每次更新一个点，大概是 O(Q + N^3) 的吧。

/*
    Name:
    Author: Gensokyo_Alice
    Date:
    Description:
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <ctime>
#include <stack>
#include <queue>
#include <set>
#include <map>

using namespace std;

typedef long long ll;
const ll MAXN = (1LL << 20) + 10, INF = 0x3f3f3f3f3f3f3f3f;

template<typename T> void read(T& x) {
    char s = getchar(); x = 0; long long f = 1;
    for (; !isdigit(s); s = getchar()) if (s == '-') f = -1;
    for (; isdigit(s); s = getchar()) x = 10 * x + (s - '0');
    x *= f;
}

ll N, M, Q, f[210][210], tim[MAXN], head[MAXN], cnt = -1, dfn[MAXN];

struct edge {
    ll x, y, v;
} e[MAXN];

struct edg {
    ll nt, to, v;
} E[MAXN];

struct que {
    ll x, y, tim;
    friend bool operator < (que a, que b) {return a.tim < b.tim;}
} q[MAXN];

void debug() {
    for (ll i = 1; i <= N; i++, puts(""))
        for (ll j = 1; j <= N; j++)
            if (f[i][j] != INF) printf("%lld ", f[i][j]);
            else printf("%lld ", -1LL);
}

int main() {
    memset(tim, 0x3f, sizeof(tim));
    memset(f, 0x3f, sizeof(f));
    memset(head, -1, sizeof(head));
    read(N); read(M);
    for (ll i = 1; i <= N; i++) read(tim[i]), dfn[i] = i, f[i][i] = 0;
    for (ll i = 1; i <= M; i++) read(e[i].x), e[i].x++, read(e[i].y), e[i].y++, read(e[i].v), f[e[i].x][e[i].y] = f[e[i].y][e[i].x] = min(f[e[i].x][e[i].y], e[i].v);
    read(Q);
    for (ll i = 1; i <= Q; i++) read(q[i].x), q[i].x++, read(q[i].y), q[i].y++, read(q[i].tim);
    for (ll i = 1, l = 1; i <= Q; i++) {
        while (l <= N && tim[dfn[l]] <= q[i].tim) {
            ll now = dfn[l];
            for (ll i = 1; i <= N; i++)
                for (ll j = 1; j <= N; j++)
                    if (i != j && i != now && j != now)
                        f[i][j] = min(f[i][j], f[i][now] + f[now][j]);
            l++;
            //debug();
        }
        if (f[q[i].x][q[i].y] >= INF || tim[q[i].x] > q[i].tim || tim[q[i].y] > q[i].tim) puts("-1");
        else printf("%lld\n", f[q[i].x][q[i].y]);
    }
    return 0;
}