Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

水题笔记 康复训练的板子 [模板]

Posted on Edited on In

草 大学太难了 我想回高中

我为什么不好好学OI

已经不会写代码了 进行康复训练

线段树

还算顺手

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define LL long long
#define LS(x) ((x) << 1)
#define RS(x) (((x) << 1) | 1)
using namespace std;
struct node {
    int le, ri, lazy;
    LL zh;
} tree[MAXN << 3];
int a[MAXN];
void build(int now, int le, int ri) {
    tree[now].le = le, tree[now].ri = ri;
    if (le == ri) {
        tree[now].zh = a[le];
        return ;
    }
    int mi = (le + ri) >> 1;
    build(LS(now), le, mi), build(RS(now), mi + 1, ri);
    tree[now].zh = tree[LS(now)].zh + tree[RS(now)].zh;
    return ;
}
void push_down(int now) {
    int& zh = tree[now].lazy;
    tree[LS(now)].lazy += zh, tree[RS(now)].lazy += zh;
    tree[LS(now)].zh += (LL)(tree[LS(now)].ri - tree[LS(now)].le + 1) * zh;
    tree[RS(now)].zh += (LL)(tree[RS(now)].ri - tree[RS(now)].le + 1) * zh;
    zh = 0;
}
void adjust(int now, int tle, int tri, int k) {
    tree[now].zh += (LL)(tri - tle + 1) * k;
    push_down(now);
    if (tree[now].le == tle && tree[now].ri == tri) {
        tree[now].lazy += k;
        return ;
    }
    int mi = (tree[now].le + tree[now].ri) >> 1;
    if (tri <= mi)    adjust(LS(now), tle, tri, k);
    else if (tle > mi)  adjust(RS(now), tle, tri, k);
    else    adjust(LS(now), tle, mi, k), adjust(RS(now), mi + 1, tri, k);
    return ;
}
LL enquiry(int now, int le, int ri) {
    if (tree[now].le == le && tree[now].ri == ri)
        return tree[now].zh;
    push_down(now);
    int mi = (tree[now].le + tree[now].ri) >> 1;
    if (ri <= mi)    return enquiry(LS(now), le, ri);
    else if (le > mi) return enquiry(RS(now), le, ri);
    else return enquiry(LS(now), le, mi) + enquiry(RS(now), mi + 1, ri);
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);
    for (int i = 1, a, b, c, d; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        if (a == 1) {
            scanf("%d", &d);
            adjust(1, b, c, d);
        }
        else
            printf("%lld\n", enquiry(1, b, c));
    }
    return 0;
}

快速幂

别忘了在指数为\(0\)或\(1\)的时候模个\(p\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
LL p, num;
LL fastpow(int k) {
    if (k == 0) return 1 % p;
    if (k == 1) return num % p;
    LL re = fastpow(k >> 1);
    re = (re * re) % p;
    if (k & 1) re = (re * num) % p;
    return re;
}
int main() {
    int k;
    scanf("%lld%d%lld", &num, &k, &p);
    printf("%lld^%d mod %lld=%lld", num, k, p, fastpow(k));
    return 0;
}

并查集

居然一遍过了真是感动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (10000)
#define swap(x, y) { int t = x; x = y; y = t; }
using namespace std;
struct node {
    int fa, size;
} a[MAXN + 5];
int find(int x) { return ((a[x].fa == x) ? x : (a[x].fa = find(a[x].fa))); }
void merge(int x, int y) {
    x = find(x), y = find(y);
    if (a[x].size < a[y].size) swap(x, y);
    a[y].fa = x, a[x].size += a[y].size;
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        a[i].fa = i, a[i].size = 1;
    for (int i = 1, x, y, z; i <= m; i++) {
        scanf("%d%d%d", &z, &x, &y);
        if (z & 1) merge(x, y);
        else puts(find(x) == find(y) ? "Y" : "N");
    }
    return 0;
}

最短路

感觉priority_queue自己的优先级比较诡异, 最好自己写cmp 然后就是memest里的0x7f和直接赋值的0x7fffffff好像并不是一回事, 有空瞅两眼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define INF (2147483647)
#define MAXN (10000)
#define MAXM (500000)
#define pii pair<int, int>
using namespace std;
struct edge {
    int x, y, cost, next;
} e[MAXM + 5];
int n, m, g[MAXN + 5], cnte, dis[MAXN + 5], s;
bool vis[MAXN + 5];
void adde(int x, int y, int c) {
    ++cnte;
    e[cnte].x = x, e[cnte].y = y, e[cnte].cost = c, e[cnte].next = g[x];
    g[x] = cnte;
}
void dijk() {
    dis[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > q;
    q.push(make_pair(0, s));
    while (!q.empty()) {
        int nown = q.top().second;
        q.pop();
        if (vis[nown]) continue;
        vis[nown] = true;
        for (int i = g[nown]; i; i = e[i].next)
            if (dis[e[i].y] > dis[nown] + e[i].cost)
                q.push(make_pair(dis[e[i].y] = dis[nown] + e[i].cost, e[i].y));
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= n; i++) dis[i] = INF;
    memset(vis, false, sizeof(vis));
    for (int i = 1, x, y, c; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &c);
        adde(x, y, c);
    }
    dijk();
    for (int i = 1; i <= n; i++)
        printf("%d ", dis[i]);
    return 0;
}

线性筛

一开始写成埃氏筛了... 重点看注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long 
#define MAXN (100000000)
#define MAXP (100000)
using namespace std;
bool isp[MAXN + 5];
int prim[MAXP + 5];
int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    memset(isp, true, sizeof(isp));
    isp[1] = false;
    for (int i = 1; i <= n; i++) {
        if (isp[i])
            prim[++prim[0]] = i;
        for (int j = 1; j <= prim[0] && (LL)i * prim[j] <= n; j++) {
            isp[i * prim[j]] = false;
            if (i % prim[j] == 0) break; 
        }
    }
    for (int i = 1, k; i <= q; i++) {
        scanf("%d", &k);
        printf("%d\n", prim[k]);
    }
    return 0;
}

最小生成树

开始数组开小了 = =

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (5000)
#define MAXM (200000)
using namespace std;
struct edge {
    int from, to, cost;
} b[MAXM + 5];
struct node {
    int size, fa;
} a[MAXN + 5];
int find(int x) { return (a[x].fa == x) ? x : (a[x].fa = find(a[x].fa)); }
void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (a[fx].size > a[fy].size)
        a[fx].size += a[fy].size, a[fy].fa = fx;
    else
        a[fy].size += a[fx].size, a[fx].fa = fy;
}
bool cmp(edge& x, edge& y) { return x.cost < y.cost; }
int n, m, ans;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) a[i].fa = i, a[i].size = 1;
    for (int i = 1; i <= m; i++) scanf("%d%d%d", &b[i].from, &b[i].to, &b[i].cost);
    sort(b + 1, b + m + 1, cmp);
    for (int i = 1, cnte = 0; i <= m; i++)
        if (find(b[i].from) != find(b[i].to)) {
            ans += b[i].cost, ++cnte;
            merge(b[i].from, b[i].to);
            if (cnte == n - 1) break;
        }
    if (a[find(1)].size != n) puts("orz");
    else printf("%d", ans);
    return 0;
}

字符串哈希

日他妈 什么模数都赶不上他妈的自然溢出 绝了

注意利用sort和unique来找种类数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define ULL unsigned long long 
#define MAXS 1500
#define MAXN 10000
using namespace std;
ULL hsa[MAXN + 5];
int ans;
int main() {
    int n, sn;
    char nows[MAXS + 5];
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", nows);
        sn = strlen(nows);
        ULL nowi = 0;
        for (int j = 0; j <= sn; j++) {
            nowi = nowi * 62;
            if (nows[j] >= '0' && nows[j] <= '9')
                nowi += nows[j] - '0';
            else if (nows[j] >= 'a' && nows[j] <= 'z')
                nowi += nows[j] - 'a' + 10;
            else
                nowi += nows[j] - 'A' + 36;
        }
        hsa[++hsa[0]] = nowi;
    }
    sort(hsa, hsa + n + 1);
    printf("%d", unique(hsa, hsa + n + 1) - hsa - 1);
    return 0;
}

单调队列

数组开小了一次, 感觉还不错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000)
#define INF (0x7fffffff)
#define pii pair<int, int>
using namespace std;
int n, k, a[MAXN + 5], head1, tail1, head2, tail2;
pii q1[MAXN + 5], q2[MAXN + 5], ans[MAXN + 5];
void push(pii x) {
    while (tail1 >= head1 && x.first < q1[tail1].first)
        --tail1;
    q1[++tail1] = x;
    while (tail2 >= head2 && x.first > q2[tail2].first)
        --tail2;
    q2[++tail2] = x;
}
void query(int x) {
    while (q1[head1].second <= x - k) ++head1;
    while (q2[head2].second <= x - k) ++head2;
    ans[x] = make_pair(q1[head1].first, q2[head2].first);
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) push(make_pair(a[i], i)), query(i);
    for (int i = k; i <= n; i++) printf("%d ", ans[i].first);
    puts("");
    for (int i = k; i <= n; i++) printf("%d ", ans[i].second);
    return 0;
}

LCA

差点不会树剖了= =

注意跳重链的时候比较的是跳之后的深度

还有别忘了轻儿子的top是他自己(真的会有人忘了吗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (500000)
using namespace std;
struct node {
    int fa, top, size, hs, deep;
} a[MAXN + 5];
struct edg {
    int from, to, next;
} b[(MAXN << 1) + 5];
int root, n, g[MAXN + 5], cntb, q;
void ade(int fr, int t) {
    b[++cntb] = {fr, t, g[fr]};
    g[fr] = cntb;
}
void init(int now) {
    a[now].size = 1, a[now].deep = a[a[now].fa].deep + 1;
    for (int i = g[now]; i; i = b[i].next)
        if (b[i].to != a[now].fa) {
            a[b[i].to].fa = now;
            init(b[i].to);
            if (a[b[i].to].size > a[a[now].hs].size) a[now].hs = b[i].to;
            a[now].size += a[b[i].to].size;
        }
}
void dfs(int now) {
    if (a[now].hs) a[a[now].hs].top = a[now].top, dfs(a[now].hs);
    for (int i = g[now]; i; i = b[i].next)
        if (b[i].to != a[now].fa && b[i].to != a[now].hs)
            a[b[i].to].top = b[i].to, dfs(b[i].to);
}
int lca(int x, int y) {
    while (a[x].top != a[y].top) {
        if (a[a[x].top].deep < a[a[y].top].deep) swap(x, y);
        x = a[a[x].top].fa;
    }
    if (a[x].deep > a[y].deep) swap(x, y);
    return x;
}
int main() {
    scanf("%d%d%d", &n, &q, &root);
    for (int i = 1, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        ade(x, y), ade(y, x);
    }
    a[root].top = a[root].fa = root;
    init(root), dfs(root);
    for (int i = 1, x, y; i <= q; i++) {
        scanf("%d%d", &x, &y);
        printf("%d\n", lca(x, y));
    }
    return 0;
}

最小费用最大流

妈的这比dinic不知道好写到哪里去了

好像常数略大 不开氧气过不去很蛋疼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (5000)
#define MAXM (50000)
#define INF (0x7fffffff)
#define rev(i) ((((i) - 1) ^ 1) + 1)
using namespace std;
struct edg {
    int from, to, cost, flow, cap, next;
} b[(MAXM << 1) + 5];
int g[MAXN + 5], cntb, n, m, pre[MAXN], s, t, ansf, ansc;
void ade(int fr, int t, int ca, int co) {
    b[++cntb] = {fr, t, co, 0, ca, g[fr]};
    g[fr] = cntb;
}
int spfa() {
    queue<int> q;
    int dis[MAXN + 5], a[MAXN + 5];
    bool inq[MAXN + 5];
    memset(dis, 0x7f, sizeof(dis));
    memset(inq, false, sizeof(inq));
    memset(a, 0, sizeof(a));
    a[s] = INF, dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        inq[now] = false;
        for (int i = g[now]; i; i = b[i].next)
            if (b[i].flow < b[i].cap && dis[b[i].to] > dis[now] + b[i].cost) {
                dis[b[i].to] = dis[now] + b[i].cost;
                pre[b[i].to] = i;
                a[b[i].to] = min(a[now], b[i].cap - b[i].flow);
                if (!inq[b[i].to]) inq[b[i].to] = true, q.push(b[i].to);
            }
    }
    return a[t];
}
void solve() {
    int nans;
    while (nans = spfa()) {
        ansf += nans;
        for (int i = t; i != s; i = b[pre[i]].from)
            b[pre[i]].flow += nans, b[rev(pre[i])].flow -= nans, ansc += nans * b[pre[i]].cost;
    }
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1, ui, vi, wi, fi; i <= m; i++) {
        scanf("%d%d%d%d", &ui, &vi, &wi, &fi);
        ade(ui, vi, wi, fi);
        ade(vi, ui, 0, -fi);
    }
    solve();
    printf("%d %d", ansf, ansc);
    return 0;
}

最大流

忘写了一些东西 当前弧优化实属op

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (200)
#define MAXM (5000)
#define INF (2139062143)
#define rev(i) ((((i) - 1) ^ 1) + 1)
#define LL long long
using namespace std;
struct edg {
    int from, to, next, cap, flow;
} b[(MAXM << 1) + 5];
int g[MAXN + 5], cntb, n, m, s, t, dis[MAXN + 5], cur[MAXN + 5];
LL ans;
void ade(int fr, int tr, int ca) {
    b[++cntb] = {fr, tr, g[fr], ca, 0};
    g[fr] = cntb;
}
bool bfs() {
    for (int i = 1; i <= n; i++) cur[i] = g[i];
    memset(dis, 0, sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s] = 1;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = g[now]; i; i = b[i].next)
            if (b[i].cap > b[i].flow && !dis[b[i].to])
                dis[b[i].to] = dis[now] + 1, q.push(b[i].to);
    }
    return dis[t];
}
LL dinic(int now, int maxf) {
    LL re = 0, zl;
    if (now == t || !maxf) return maxf;
    for (int i = cur[now]; i; i = b[i].next)
        if (b[i].cap > b[i].flow && dis[b[i].to] == dis[now] + 1) {
            cur[now] = i;
            zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
            maxf -= zl; 
            b[i].flow += zl;
            b[rev(i)].flow -= zl;
            re += zl;
        }
    return re;
}
void solve() {
    while (bfs())
        ans += dinic(s, INF);
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1, ui, vi, wi; i <= m; i++) {
        scanf("%d%d%d", &ui, &vi, &wi);
        ade(ui, vi, wi), ade(vi, ui, 0);
    }
    solve();
    printf("%lld", ans);
    return 0;
}

缩点

妈的把i和j搞混了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define MAXN (10000)
#define MAXM (100000)
using namespace std;
struct edg {
    int from, to, next;
} b[MAXM + 5], nb[MAXM + 5];
int g[MAXN + 5], ng[MAXN + 5], n, m, cntb, ncntb, belong[MAXN + 5], f[MAXN + 5], dfn[MAXN + 5], low[MAXN + 5], cntdfn, a[MAXN + 5], 
    na[MAXN + 5];
bool ins[MAXN + 5];
stack<int> gary;
void ade(int* dg, edg* db, int&dcntb, int fr, int tr) {
    db[++dcntb] = {fr, tr, dg[fr]};
    dg[fr] = dcntb;
}
void tarjan(int now) {
    belong[now] = now;
    low[now] = dfn[now] = ++cntdfn;
    ins[now] = true;
    gary.push(now);
    for (int i = g[now]; i; i = b[i].next)
        if (ins[b[i].to])
            low[now] = min(low[now], dfn[b[i].to]);
        else if (!dfn[b[i].to])
            tarjan(b[i].to), low[now] = min(low[now], low[b[i].to]);
    if (low[now] == dfn[now]) {
        while (gary.top() != now) {
            ins[gary.top()] = false;
            belong[gary.top()] = now;
            gary.pop();
        }
        gary.pop();
        ins[now] = false;
    }
}
int dfs(int now) {
    if (f[now] >= 0) return f[now];
    f[now] = na[now]; 
    for (int i = ng[now]; i; i = nb[i].next)
        f[now] = max(f[now], na[now] + dfs(nb[i].to));
    return f[now];
}
void solve() {
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= n; i++) {
        na[belong[i]] += a[i];
        for (int j = g[i]; j; j = b[j].next)
            if (belong[b[j].to] != belong[b[j].from])
                ade(ng, nb, ncntb, belong[b[j].from], belong[b[j].to]);
    }
    memset(f, -1, sizeof(f));
    for (int i = 1; i <= n; i++)
        if (f[belong[i]] == -1)
            dfs(belong[i]);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, f[belong[i]]);
    printf("%d", ans);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1, ui, vi; i <= m; i++) scanf("%d%d", &ui, &vi), ade(g, b, cntb, ui, vi);
    solve();
    return 0;
}

Nim

想在洛谷上刷通过数的是不是多多少少都有点...?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, ans = 0;
        scanf("%d", &n);
        for (int i = 1, ai; i <= n; i++)
            scanf("%d", &ai), ans ^= ai;
        puts(ans ? "Yes" : "No");
    }
    return 0;
}

负权多源最短路

这题有点意思 把每条边的边权变为b[i].cost - dis[0][b[i].from] + dis[0][b[i].to]这样以来在求最短路的时候中间部分能全部消掉, 而用Bellman-ford预处理的时候已经保证了dis[0][b[i].from] + cost >= dis[0][b[i].to]](不然就松弛了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (3000)
#define MAXM (6000)
#define INF (1000000000)
#define LL long long
#define pii pair<int, int>
using namespace std;
struct edg {
    int from, to, cost, next;
} b[MAXM + MAXN + 5];
struct cmp {
    bool operator () (const pii x, const pii y) { return x.second > y.second; }
};
int g[MAXN + 5], cntb, n, m, hdis[MAXN + 5], dis[MAXN + 5];
bool vis[MAXN + 5];
LL ans;
void ade(int fr, int tr, int cr) {
    b[++cntb] = {fr, tr, cr, g[fr]};
    g[fr] = cntb;
}
bool bellmanFord() {
    for (int i = 1; i <= n; i++) ade(0, i, 0);
    memset(hdis, 0x7f, sizeof(hdis));
    hdis[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= cntb; j++)
            if (hdis[b[j].from] < INF)
                hdis[b[j].to] = min(hdis[b[j].to], hdis[b[j].from] + b[j].cost);
    for (int i = 1; i <= cntb; i++)
        if (hdis[b[i].to] > hdis[b[i].from] + b[i].cost)
            return false;
    return true;
}
void dijk(int s) {
    priority_queue<pii, vector<pii>, cmp> q;
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= n; i++) dis[i] = INF;
    dis[s] = 0;
    q.push(make_pair(s, 0));
    while (!q.empty()) {
        int now = q.top().first;
        q.pop();
        if (vis[now]) continue;
        vis[now] = true;
        for (int i = g[now]; i; i = b[i].next)
            if (dis[b[i].to] > dis[now] + b[i].cost)
                dis[b[i].to] = dis[now] + b[i].cost, q.push(make_pair(b[i].to, dis[b[i].to]));
    }
    ans = 0;
    for (int i = 1; i <= n; i++)
        if (dis[i] != INF)
            ans += (LL)i * (dis[i] - hdis[s] + hdis[i]);
        else
            ans += (LL)i * INF;
    printf("%lld\n", ans);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, ui, vi, ci; i <= m; i++)
        scanf("%d%d%d", &ui, &vi, &ci), ade(ui, vi, ci);
    if (!bellmanFord()) {
        puts("-1");
        return 0;
    }
    for (int i = 1; i <= cntb; i++)
        b[i].cost += hdis[b[i].from], b[i].cost -= hdis[b[i].to];
    for (int i = 1; i <= n; i++) dijk(i);
    return 0;
}

By Cansult