MENU

JzxxOJ3498 旅程

JzxxOJ3498

离线动态图floyd模板,反向处理,删边变为加边。

#include<cstdio>
#if _WIN32||__WIN32__||_WIN64||__WIN64__||__CYGWIN__
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_WARNINGS
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#if __unix__
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#if __GNUC__
#define inline __attribute__((always_inline))
#endif
struct io {
    static const int L = (1 << 23) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void putc(char x) {
        *oS++ = x;
        if (oS == oT)fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
    }
    char gc() {
        if (iS == iT)iT = (iS = ibuf) + fread(ibuf, 1, L, stdin);
        return *iS++;
    }
    template<class T>T rd() {
        int c = gc();
        T x = 0;
        for (; c < 48 || c > 57; c = gc());
        for (; c > 47 && c < 58; c = gc())x = x * 10 + (c & 15);
        return x;
    }
    template<class T>void print(T x) {
        if (!x) { putc('0'); return; }
        if (x < 0)putc('-'), x = -x;
        int tp = 0;
        for (; x; st[++tp] = x % 10 + 48, x /= 10);
        for (; tp; *oS++ = st[tp--]);
    }
    io() :oS(obuf), oT(obuf + L - 1) {
#ifndef ONLINE_JUDGE
        freopen("journey.in", "r", stdin), freopen("journey.out", "w", stdout);
#endif
    }
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int n = ip.rd<int>(), m = ip.rd<int>(), f[201][201], ans[100001], cnt;
struct node {
    int opt, x, y, w;
    node() {}
    node(int opt, int x, int y) :opt(opt), x(x), y(y) {}
}nd[100001];
int main() {
    for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)f[i][j] = ip.rd<int>();
    for (int i = 1; i <= m; ++i) {
        int opt = ip.rd<int>(), x = ip.rd<int>(), y = ip.rd<int>();
        nd[i] = node(opt, x, y);
        if (opt == 1)nd[i].w = f[x][y], f[x][y] = 0x3f3f3f3f;
    }
    for (int k = 1; k <= n; ++k)for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j) {
        int t = f[i][k] + f[k][j];
        if (f[i][j] > t)f[i][j] = t;
    }
    for (int k = m; k; --k) {
        node cur = nd[k];
        if (cur.opt == 1)for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j) {
            int t = f[i][cur.x] + cur.w + f[cur.y][j];
            if (f[i][j] > t)f[i][j] = t;
        }
        else ans[++cnt] = f[cur.x][cur.y];
    }
    for (int i = cnt; i; --i) {
        int t = ans[i];
        ip.print(t >= 0x3f3f3f ? -1 : t), ip.putc('\n');
    }
}