GESP C++ 七级历年真题题解

_Separation 2026-5-17 20:30:36 25 浏览 0 点赞 0 收藏

#GESP

GESP C++ 七级历年真题题解

1. 迷宫统计

题目大意

给定一个 $n \times n$ 的邻接矩阵，表示 $n$ 个迷宫之间是否可以直接到达。对于指定迷宫 $m$ ，要求输出：

$m$ 可以直接到达多少个迷宫；
有多少个迷宫可以直接到达 $m$ ；
二者之和。

注意每个迷宫都可以直接到达自己。

解题思路

邻接矩阵中：

第 $m$ 行表示从 $m$ 出发可以到达哪些点；
第 $m$ 列表示哪些点可以到达 $m$ 。

所以直接统计第 $m$ 行和第 $m$ 列中 $1$ 的个数即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
int a[N][N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    int out = 0, in = 0;
    for (int j = 1; j <= n; j++) if (a[m][j]) out++;
    for (int i = 1; i <= n; i++) if (a[i][m]) in++;
    printf("%d %d %d\n", out, in, out + in);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

2. 最长不下降子序列

题目大意

给定一个有向无环图，每个点有一个点权 $A_i$ 。对于图中的任意一条路径，可以得到路径上的点权序列。要求在所有路径中，求最长不下降子序列的最大长度。点权满足 $A_i \le 10$ 。

解题思路

因为图是 $\text{DAG}$ ，可以拓扑排序。

由于点权只有 $1 \sim 10$ ，可以对每个点维护一个数组：

dp[u][v]

表示走到点 $u$ 时，已经得到的最长不下降子序列中，最后一个被选中的值为 $v$ 的最大长度。

处理点 $u$ 时，可以选择把 $u$ 加入子序列。若 $A_u=w$ ，则可以从所有 $v \le w$ 的状态转移过来：

dp[u][w]=\max(dp[u][w],\max_{v\le w}dp[u][v]+1)

然后把 $u$ 的状态沿有向边传播给后继点。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
int a[N], deg[N];
int dp[N][11];
vector<int> g[N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        deg[v]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!deg[i]) q.push(i);
    }
    int Ans = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        int w = a[u], best = 0;
        for (int v = 1; v <= w; v++) best = max(best, dp[u][v]);
        dp[u][w] = max(dp[u][w], best + 1);
        for (int v = 1; v <= 10; v++) Ans = max(Ans, dp[u][v]);
        for (int to : g[u]) {
            for (int v = 1; v <= 10; v++) {
                dp[to][v] = max(dp[to][v], dp[u][v]);
            }
            deg[to]--;
            if (!deg[to]) q.push(to);
        }
    }
    printf("%d\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

3. 商品交易

题目大意

有 $N$ 种商品，每种商品有价值 $v_i$ 。若某个商人支持用商品 $x$ 换商品 $y$ ，则你可以从 $x$ 变成 $y$ 。交换时还要支付：

v_y-v_x+1

其中 $1$ 是手续费。现在你初始拥有商品 $a$ ，希望得到商品 $b$ ，求最少花费；若无法得到，输出 $\text{No solution}$ 。

解题思路

一条路径：

a \to p_1 \to p_2 \to \cdots \to b

总费用为：

$$(v_{p_1}-v_a+1)+(v_{p_2}-v_{p_1}+1)+\cdots+(v_b-v_{last}+1) $$

中间价值会全部抵消，得到：

v_b-v_a+\text{交换次数}

因此只需要求从 $a$ 到 $b$ 的最少边数。

用 $\text{BFS}$ 求最短路边数即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m, a, b;
LL val[N];
vector<int> g[N];
int dis[N];
inline void solve() {
    cin >> n >> m >> a >> b;
    for (int i = 0; i < n; i++) cin >> val[i];
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
    }
    for (int i = 0; i < n; i++) dis[i] = -1;
    queue<int> q;
    q.push(a);
    dis[a] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    if (dis[b] == -1) printf("No solution\n");
    else printf("%lld\n", val[b] - val[a] + dis[b]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

4. 纸牌游戏

题目大意

你和小杨各有 $0,1,2$ 三张牌。每轮双方各出一张牌，规则为：

$1$ 胜 $0$ ；
$2$ 胜 $1$ ；
$0$ 胜 $2$ ；
相同则平局。

第 $i$ 轮胜者得 $2a_i$ 分，平局双方得 $a_i$ 分。小杨提前告诉你每轮出什么牌。你从第二轮开始可以选择是否换牌，若总共换了 $t$ 次，要额外扣除 $b_1+\cdots+b_t$ 分。求你最多能得多少分。

解题思路

动态规划。

设：

dp[i][c][t]

表示前 $i$ 轮结束后，第 $i$ 轮你出牌 $c$ ，总共换了 $t$ 次时的最大得分。

第 $1$ 轮可以任意出牌，不产生换牌罚分。

从第 $i-1$ 轮转移到第 $i$ 轮时：

若牌不变，换牌次数不变；
若牌改变，换牌次数 $+1$ ，并扣除对应的 $b_t$ 。

最后在所有状态中取最大值。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
LL a[N], b[N];
int c[N];
LL dp[N][3][N];
LL get(int x, int y, int i) {
    if (x == y) return a[i];
    if ((x == 1 && y == 0) || (x == 2 && y == 1) || (x == 0 && y == 2)) {
        return 2 * a[i];
    }
    return 0;
}
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k <= n; k++) {
                dp[i][j][k] = -inf;
            }
        }
    }
    for (int x = 0; x < 3; x++) {
        dp[1][x][0] = get(x, c[1], 1);
    }
    for (int i = 2; i <= n; i++) {
        for (int pre = 0; pre < 3; pre++) {
            for (int t = 0; t <= i - 2; t++) {
                if (dp[i - 1][pre][t] == -inf) continue;
                for (int now = 0; now < 3; now++) {
                    int nt = t + (now != pre);
                    LL val = dp[i - 1][pre][t] + get(now, c[i], i);
                    if (now != pre) val -= b[nt];
                    dp[i][now][nt] = max(dp[i][now][nt], val);
                }
            }
        }
    }
    LL Ans = -inf;
    for (int x = 0; x < 3; x++) {
        for (int t = 0; t < n; t++) {
            Ans = max(Ans, dp[n][x][t]);
        }
    }
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

5. 交流问题

题目大意

有 $n$ 名同学来自 $A,B$ 两所学校。题目给出 $m$ 次交流，每次交流的两名同学一定来自不同学校。现在只知道交流关系，要求推断 $B$ 校人数的最小值和最大值。

解题思路

因为每条边连接的两端一定来自不同学校，所以整张图是二分图。

对于每个连通块，二分染色后会得到两部分，大小分别为 $x,y$ 。

这个连通块中哪一部分属于 $B$ 校是不确定的，所以：

对最小值贡献 $\min(x,y)$ ；
对最大值贡献 $\max(x,y)$ 。

孤立点可以属于任意学校，所以对最小值贡献 $0$ ，对最大值贡献 $1$ 。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
vector<int> g[N];
int col[N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int mn = 0, mx = 0;
    for (int s = 1; s <= n; s++) {
        if (col[s]) continue;
        if (g[s].empty()) {
            col[s] = 1;
            mx++;
            continue;
        }
        int cnt[3] = {0, 0, 0};
        queue<int> q;
        q.push(s);
        col[s] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            cnt[col[u]]++;
            for (int v : g[u]) {
                if (!col[v]) {
                    col[v] = 3 - col[u];
                    q.push(v);
                }
            }
        }
        mn += min(cnt[1], cnt[2]);
        mx += max(cnt[1], cnt[2]);
    }
    printf("%d %d\n", mn, mx);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

6. 俄罗斯方块

题目大意

给定一个 $n \times m$ 的颜色网格。同色且四连通的一组格子构成一个俄罗斯方块。两个俄罗斯方块只要可以通过平移重合，就认为是同一种；颜色不同也仍可视为同一种。求不同种类的俄罗斯方块数量。

解题思路

先用 $\text{BFS}$ 找出每个同色连通块。

对于一个连通块，记录所有格子的坐标。为了判断平移后是否相同，需要做归一化：

找到连通块中最小的行号 $mnx$ 和最小的列号 $mny$ ；
所有坐标都减去 $(mnx,mny)$ ；
排序后转成字符串，放入 $\text{set}$ 中。

最后 $\text{set}$ 的大小就是答案。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
int a[510][510], vis[510][510];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
set<string> st;
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (vis[i][j]) continue;
            vector<pair<int, int> > v;
            queue<pair<int, int> > q;
            q.push({i, j});
            vis[i][j] = 1;
            int col = a[i][j];
            while (!q.empty()) {
                auto p = q.front(); q.pop();
                int x = p.first, y = p.second;
                v.push_back({x, y});
                for (int d = 0; d < 4; d++) {
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
                    if (vis[nx][ny]) continue;
                    if (a[nx][ny] != col) continue;
                    vis[nx][ny] = 1;
                    q.push({nx, ny});
                }
            }
            int mnx = n + 1, mny = m + 1;
            for (auto p : v) {
                mnx = min(mnx, p.first);
                mny = min(mny, p.second);
            }
            vector<pair<int, int> > b;
            for (auto p : v) {
                b.push_back({p.first - mnx, p.second - mny});
            }
            sort(b.begin(), b.end());
            string s;
            for (auto p : b) {
                s += to_string(p.first);
                s += ",";
                s += to_string(p.second);
                s += ";";
            }
            st.insert(s);
        }
    }
    printf("%d\n", st.size());
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

7. 黑白翻转

题目大意

给定一棵树，每个节点是白色或黑色。每次可以把一个白色节点变成黑色。若删除所有白色节点后，剩余黑色节点仍然连成一棵树，则称原树是美丽树。求最少需要翻转多少个白色节点。

解题思路

黑色节点最终必须连通。

在树中，要让若干黑点连通，必须把所有黑点之间路径上的节点都变成黑色。

所以需要找到 包含所有初始黑点的最小连通子树 。

一条边会出现在这棵最小子树中，当且仅当：

它一侧子树中有黑点；
另一侧也有黑点。

设这棵最小子树有 $E$ 条边，那么它有 $E+1$ 个点。

答案为：

(E+1)-\text{初始黑点数量}

如果初始黑点数量不超过 $1$ ，答案为 $0$ 。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
int a[N], fa[N], sub[N];
vector<int> g[N], ord;
inline void solve() {
    cin >> n;
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i]) tot++;
    }
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    if (tot <= 1) {
        printf("0\n");
        return;
    }
    queue<int> q;
    q.push(1);
    fa[1] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ord.push_back(u);
        for (int v : g[u]) {
            if (v == fa[u]) continue;
            fa[v] = u;
            q.push(v);
        }
    }
    LL edge = 0;
    for (int i = (int)ord.size() - 1; i >= 0; i--) {
        int u = ord[i];
        sub[u] += a[u];
        if (u != 1) {
            if (sub[u] > 0 && sub[u] < tot) edge++;
            sub[fa[u]] += sub[u];
        }
    }
    printf("%lld\n", edge + 1 - tot);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

8. 区间乘积

题目大意

给定一个长度为 $n$ 的正整数序列 $A$ ，统计有多少个区间 $[l,r]$ ，满足：

a_l \times a_{l+1} \times \cdots \times a_r

是完全平方数。题目中 $a_i \le 30$ 。

解题思路

一个数是完全平方数，当且仅当每个质因子的指数都是偶数。

由于 $a_i \le 30$ ，只涉及 $30$ 以内的质数。可以把每个 $a_i$ 表示为一个二进制状态，某个质因子的指数为奇数则对应位为 $1$ ，否则为 $0$ 。

区间乘积的奇偶指数状态等于前缀异或：

pre_r \oplus pre_{l-1}

如果它为 $0$ ，说明区间乘积是完全平方数。

因此只要统计相同前缀状态出现次数即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
int p[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
LL cnt[1 << 10];
int get(int x) {
    int mask = 0;
    for (int i = 0; i < 10; i++) {
        int c = 0;
        while (x % p[i] == 0) {
            x /= p[i];
            c ^= 1;
        }
        if (c) mask |= 1 << i;
    }
    return mask;
}
inline void solve() {
    cin >> n;
    int pre = 0;
    LL Ans = 0;
    cnt[0] = 1;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        pre ^= get(x);
        Ans += cnt[pre];
        cnt[pre]++;
    }
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

9. 矩阵移动

题目大意

给定一个只含 $\texttt{0}$ 、 $\texttt{1}$ 、 $\texttt{?}$ 的 $n \times m$ 矩阵。从左上角走到右下角，每次只能向右或向下。经过 $\texttt{1}$ 得 $1$ 分，经过其他字符不得分。你可以把不超过 $x$ 个 $\texttt{?}$ 改成 $\texttt{1}$ ，问最大得分。

解题思路

对于某一条路径，如果它经过了 $q$ 个 $\texttt{?}$ ，最多可以把其中 $\min(q,x)$ 个改成 $\texttt{1}$ 。

所以路径得分为：

\text{路径上原本的 }1\text{ 的数量}+\min(q,x)

做动态规划。

设：

dp[j][k]

表示当前处理到某一行第 $j$ 列，路径上已经把 $k$ 个 $\texttt{?}$ 计入得分时的最大分数。

每个格子可以从上方或左方转移过来。

遇到：

$\texttt{1}$ ：分数 $+1$ ；
$\texttt{0}$ ：分数不变；
$\texttt{?}$ ：若 $k < x$ ，则可以让 $k+1$ ，分数 $+1$ ；否则分数不变。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 5e3 + 10;
const int inf = 1e9;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m, x, pre[N][N], cur[N][N], base[N];
string s[N];
inline void solve() {
    cin >> n >> m >> x;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = " " + s[i];
    }
    for (int j = 0; j <= m; j++) {
        for (int k = 0; k <= x; k++) {
            pre[j][k] = -inf;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= x; k++) {
                cur[j][k] = -inf;
            }
        }
        for (int j = 1; j <= m; j++) {
            for (int i = 0; i <= x; i++) base[i] = -inf;
            for (int k = 0; k <= x; k++) {
                base[k] = max(base[k], pre[j][k]);
                if (j > 1) base[k] = max(base[k], cur[j - 1][k]);
            }
            if (i == 1 && j == 1) {
                base[0] = max(base[0], 0);
            }
            for (int k = 0; k <= x; k++) {
                if (base[k] < 0) continue;
                if (s[i][j] == '1') cur[j][k] = max(cur[j][k], base[k] + 1);
                else if (s[i][j] == '0') cur[j][k] = max(cur[j][k], base[k]);
                else {
                    if (k < x) cur[j][k + 1] = max(cur[j][k + 1], base[k] + 1);
                    else cur[j][k] = max(cur[j][k], base[k]);
                }
            }
        }
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= x; k++) {
                pre[j][k] = cur[j][k];
            }
        }
    }
    int Ans = 0;
    for (int k = 0; k <= x; k++) Ans = max(Ans, pre[m][k]);
    printf("%d\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

10. 小杨寻宝

题目大意

给定一棵树，部分节点有宝物。小杨可以任选起点移动，但每条边最多经过一次。经过有宝物的节点即可获得宝物。判断是否能获得所有宝物。

解题思路

在树中，如果一条路线不允许重复经过边，那么它本质上只能是一条简单路径。

所以所有有宝物的节点必须都位于同一条简单路径上。

等价于：包含所有宝物节点的最小连通子树，其每个节点的度数都不能超过 $2$ 。

做法：

求每个子树中宝物数量；
判断哪些边属于 包含所有宝物的最小子树 ；
统计这棵子树中每个节点的度；
若存在度数大于 $2$ 的节点，输出 $\text{No}$ ，否则输出 $\text{Yes}$ 。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
int a[N], fa[N], sub[N], deg[N];
vector<int> g[N], ord;
inline void solve() {
    cin >> n;
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        tot += a[i];
        g[i].clear();
        sub[i] = fa[i] = deg[i] = 0;
    }
    ord.clear();
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    queue<int> q;
    q.push(1);
    fa[1] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ord.push_back(u);
        for (int v : g[u]) {
            if (v == fa[u]) continue;
            fa[v] = u;
            q.push(v);
        }
    }
    for (int i = (int)ord.size() - 1; i >= 0; i--) {
        int u = ord[i];
        sub[u] += a[u];
        if (u != 1) {
            if (sub[u] > 0 && sub[u] < tot) {
                deg[u]++;
                deg[fa[u]]++;
            }
            sub[fa[u]] += sub[u];
        }
    }
    bool ok = true;
    for (int i = 1; i <= n; i++) if (deg[i] > 2) ok = false;
    if (ok) printf("Yes\n");
    else printf("No\n");
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

11. 武器购买

题目大意

有 $n$ 个武器，第 $i$ 个武器强度为 $p_i$ ，花费为 $c_i$ 。要购买若干武器，使总强度不小于 $P$ ，总花费不超过 $Q$ 。若存在方案，输出最小花费；否则输出 $\text{-1}$ 。

解题思路

这是 $0/1$ 背包。

设：

dp_j

表示达到强度 $j$ 的最小花费。

因为只关心是否达到 $P$ ，所以强度超过 $P$ 的都压缩到 $P$ 。

转移：

$$dp_{\min(P,j+p_i)}=\min(dp_{\min(P,j+p_i)},dp_j+c_i) $$

最后判断 $dp_P$ 是否不超过 $Q$ 。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, P, Q;
LL dp[N];
inline void solve() {
    cin >> n >> P >> Q;
    for (int i = 0; i <= P; i++) dp[i] = inf;
    dp[0] = 0;
    for (int i = 1, p, c; i <= n; i++) {
        cin >> p >> c;
        for (int j = P; j >= 0; j--) {
            if (dp[j] == inf) continue;
            int nj = min(P, j + p);
            dp[nj] = min(dp[nj], dp[j] + c);
        }
    }
    if (dp[P] <= Q) printf("%lld\n", dp[P]);
    else printf("-1\n");
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

12. 燃烧

题目大意

给定一棵树，每个节点有权值。选择一个初始节点引燃，燃烧只能从一个节点扩散到相邻且权值严格更小的节点。求最多能燃烧多少个节点。

解题思路

燃烧方向一定是从大权值走向小权值，所以不会形成环。

设：

dp_u

表示从节点 $u$ 开始燃烧，最多能烧到多少个节点。

则：

dp_u=1+\sum dp_v

其中 $v$ 是 $u$ 的相邻节点，且：

a_v < a_u

按照权值从小到大处理节点即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
int a[N];
LL dp[N];
vector<int> g[N];
vector<int> ord;
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ord.push_back(i);
        dp[i] = 1;
    }
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    sort(ord.begin(), ord.end(), [](int x, int y) {
        return a[x] < a[y];
    });
    LL Ans = 1;
    for (int u : ord) {
        for (int v : g[u]) {
            if (a[v] < a[u]) {
                dp[u] += dp[v];
            }
        }
        Ans = max(Ans, dp[u]);
    }
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

13. 图上移动

题目大意

给定一张无向图。对于每个起点 $i$ ，要求分别计算恰好走 $1,2,\ldots,k$ 步后，可能到达的不同节点数量。

解题思路

由于 $n \le 500$ ， $k \le 20$ ，可以使用 $\text{bitset}$ 。

用 $\text{adj[u]}$ 表示从 $u$ 一步可以到达的所有点。

对于一个起点，设当前可能位置集合为 $\text{cur}$ ，下一步集合为：

nxt=\bigcup_{u \in cur} adj[u]

每走一步输出 $\text{nxt.count()}$ 。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m, k;
bitset<505> adj[505];
inline void solve() {
    cin >> n >> m >> k;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        adj[u][v] = 1;
        adj[v][u] = 1;
    }
    for (int s = 1; s <= n; s++) {
        bitset<505> cur;
        cur[s] = 1;
        for (int step = 1; step <= k; step++) {
            bitset<505> nxt;
            for (int u = 1; u <= n; u++) {
                if (cur[u]) {
                    nxt |= adj[u];
                }
            }
            if (step > 1) printf(" ");
            printf("%d", (int)nxt.count());
            cur = nxt;
        }
        printf("\n");
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

14. 等价消除

题目大意

给定一个小写字母串。如果一个字符串能通过每次删除两个相同字符，最终删成空串，则称它可以被等价消除。求原串中有多少个子串可以被等价消除。

解题思路

一个字符串能被等价消除，当且仅当每种字符出现次数都是偶数。

用一个 $26$ 位二进制数表示前缀中每个字符出现次数的奇偶性。

若两个前缀状态相同，则它们中间的子串每个字符出现次数都是偶数。

所以问题变成统计相同前缀状态对数。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
string s;
unordered_map<int, LL> mp;
inline void solve() {
    cin >> n >> s;
    int mask = 0;
    LL Ans = 0;
    mp[0] = 1;
    for (char c : s) {
        mask ^= 1 << (c - 'a');
        Ans += mp[mask];
        mp[mask]++;
    }
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

15. 线图

题目大意

给定一个简单无向图 $G$ 。线图 $L(G)$ 中，每条原图边对应一个点；若原图中两条边共享一个端点，则线图中这两个点之间有边。求线图中的边数。

解题思路

对于原图中的一个点 $u$ ，若它的度数为 $d_u$ ，那么所有与它相连的边两两在线图中相邻，贡献：

\binom{d_u}{2}

因为原图是简单图，两条不同边最多共享一个端点，不会被重复统计。

所以答案为：

\sum_{u=1}^{n}\binom{d_u}{2}

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
LL deg[N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        deg[u]++;
        deg[v]++;
    }
    LL Ans = 0;
    for (int i = 1; i <= n; i++) Ans += deg[i] * (deg[i] - 1) / 2;
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

16. 调味平衡

题目大意

有 $n$ 种食材，每种食材有酸度 $a_i$ 和甜度 $b_i$ 。可以选择若干种食材，使总酸度等于总甜度。在满足平衡的前提下，最大化酸度与甜度之和。

解题思路

令每种食材的差值为：

d_i=a_i-b_i

价值为：

v_i=a_i+b_i

目标是选一些食材，使差值和为 $0$ ，并最大化价值和。

这是带负权下标的 $0/1$ 背包。

总差值范围为：

[-50000,50000]

用偏移量 $\text{B=50000}$ 处理负数下标。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, B = 50000;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
LL dp[N], ndp[N];
inline void solve() {
    cin >> n;
    for (int i = 0; i <= 100000; i++) dp[i] = -inf;
    dp[B] = 0;
    for (int i = 1, a, b; i <= n; i++) {
        cin >> a >> b;
        int d = a - b, v = a + b;
        for (int j = 0; j <= 100000; j++) ndp[j] = dp[j];
        for (int j = 0; j <= 100000; j++) {
            if (dp[j] == -inf) continue;
            int nj = j + d;
            if (0 <= nj && nj <= 100000) {
                ndp[nj] = max(ndp[nj], dp[j] + v);
            }
        }
        for (int j = 0; j <= 100000; j++) dp[j] = ndp[j];
    }
    printf("%lld\n", dp[B]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

17. 连通图

题目大意

给定一个无向图，可能有重边和自环。要求加入尽量少的边，使得整张图连通。输出最少需要加入的边数。

解题思路

如果图中有 $c$ 个连通块，那么至少需要：

c-1

条边把它们连接起来。

用并查集统计连通块个数即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
int fa[N];
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        int fu = find(u), fv = find(v);
        if (fu != fv) fa[fu] = fv;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) if (find(i) == i) cnt++;
    printf("%d\n", cnt - 1);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

18. 金币收集

题目大意

数轴上有 $n$ 枚金币，第 $i$ 枚金币在时刻 $t_i$ 出现在位置 $x_i$ 。小 A 从时刻 $0$ 、位置 $0$ 出发，每个时刻只能原地不动或向右走一格。若在时刻 $t_i$ 恰好位于 $x_i$ ，即可收集该金币。求最多能收集多少枚金币。

解题思路

从金币 $(x_1,t_1)$ 到金币 $(x_2,t_2)$ 可行，当且仅当：

x_2\ge x_1

并且：

x_2-x_1\le t_2-t_1

变形为：

x_2\ge x_1

t_2-x_2\ge t_1-x_1

令：

y_i=t_i-x_i

则问题变成二维偏序最长链：

x_i \text{ 非降}, \quad y_i \text{ 非降}

初始点 $(0,0)$ 要求金币满足 $y_i\ge0$ 。

按 $x$ 升序、 $y$ 升序排序，然后用树状数组维护 $y$ 维度上的最大值。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Node {
    LL x, y;
};
int n;
vector<Node> a;
vector<LL> ys;
int tr[N];
void add(int x, int v) {
    for (; x < N; x += x & -x) tr[x] = max(tr[x], v);
}
int ask(int x) {
    int res = 0;
    for (; x; x -= x & -x) res = max(res, tr[x]);
    return res;
}
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        LL x, t; cin >> x >> t;
        LL y = t - x;
        if (y >= 0) {
            a.push_back({x, y});
            ys.push_back(y);
        }
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    sort(a.begin(), a.end(), [](Node A, Node B) {
        if (A.x != B.x) return A.x < B.x;
        return A.y < B.y;
    });
    int Ans = 0;
    for (auto p : a) {
        int id = lower_bound(ys.begin(), ys.end(), p.y) - ys.begin() + 1;
        int val = ask(id) + 1;
        add(id, val);
        Ans = max(Ans, val);
    }
    printf("%d\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

19. 城市规划

题目大意

给定一张连通无向图。城市 $u$ 的建设难度定义为它到所有城市的最短路距离的最大值：

\max_{1\le i\le n} d(u,i)

求建设难度最小的城市；若有多个，输出编号最小者。

解题思路

$n \le 2000$ ， $m \le 2000$ ，可以从每个点出发做一次 $\text{BFS}$ 。

对于每个起点 $s$ ：

$\text{BFS}$ 求它到所有点的最短距离；
取最大距离作为该点建设难度；
更新答案。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, inf = 1e9;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
vector<int> g[2010];
int dis[2010];
int bfs(int s) {
    for (int i = 1; i <= n; i++) dis[i] = -1;
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, dis[i]);
    }
    return res;
}
inline void solve() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int Ans = 1, best = inf;
    for (int i = 1; i <= n; i++) {
        int cur = bfs(i);
        if (cur < best) {
            best = cur;
            Ans = i;
        }
    }
    printf("%d\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

20. 学习小组

题目大意

有 $n$ 名同学，第 $i$ 名同学发言积极度为 $c_i$ 。若一个小组有 $k$ 人，则基础积极度为 $a_k$ ，综合积极度为：

a_k+\max(c)-\min(c)

要把所有同学划分成若干小组，求综合积极度总和最大值。

解题思路

先把 $c_i$ 从小到大排序。

如果最终有 $g$ 个小组人数至少为 $2$ ，那么为了最大化所有小组的：

\max(c)-\min(c)

应该让最小的 $g$ 个数作为这些组的最小值，最大的 $g$ 个数作为这些组的最大值。

因此范围贡献为：

(c_{n-g+1}+\cdots+c_n)-(c_1+\cdots+c_g)

剩下要解决的是：把 $n$ 人划分成若干组，且恰好有 $g$ 个组大小至少为 $2$ ，基础积极度最大是多少。

设：

dp[i][g]

表示已经分了 $i$ 个人，且其中有 $g$ 个非单人组时，基础积极度最大值。

枚举最后一组大小 $k$ ：

若 $k=1$ ，非单人组数量不变；
若 $k\ge2$ ，非单人组数量加 $1$ 。

最后枚举 $g$ 取最大值。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
LL c[310], a[310], pre[310], dp[310][310];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(c + 1, c + n + 1);
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + c[i];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = -inf;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int g = 0; g <= n; g++) {
            if (dp[i][g] == -inf) continue;
            for (int k = 1; i + k <= n; k++) {
                int ng = g + (k >= 2);
                dp[i + k][ng] = max(dp[i + k][ng], dp[i][g] + a[k]);
            }
        }
    }
    LL Ans = 0;
    for (int g = 0; 2 * g <= n; g++) {
        LL range = (pre[n] - pre[n - g]) - pre[g];
        Ans = max(Ans, dp[n][g] + range);
    }
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

21. 拆分

题目大意

给定正整数 $n$ ，把它拆成若干个正整数之和，使这些正整数的乘积最大。输出最大乘积对 $10^9$ 取模的结果。允许只拆成一个数。

解题思路

经典结论：为了让乘积最大，应尽量拆成 $3$ 。

但由于本题允许只拆成一个数，所以：

$n=1,2,3,4$ 时，答案就是 $n$ ；
$n>4$ 时，尽量拆成 $3$ 。

若：

n=3q+r

则：

$r=0$ ：答案为 $3^q$ ；
$r=1$ ：把一个 $3+1$ 改成 $2+2$ ，答案为 $3^{q-1}\times4$ ；
$r=2$ ：答案为 $3^q\times2$ 。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL mod = 1000000000LL;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
LL qpow(LL a, LL b) {
    LL res = 1 % mod;
    a %= mod;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
LL n;
inline void solve() {
    cin >> n;
    if (n <= 4) {
        printf("%lld\n", n % mod);
        return;
    }
    LL q = n / 3, r = n % 3;
    if (r == 0) printf("%lld\n", qpow(3, q));
    else if (r == 1) printf("%lld\n", qpow(3, q - 1) * 4 % mod);
    else printf("%lld\n", qpow(3, q) * 2 % mod);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

22. 物流网络

题目大意

给定一张无向图，每条边有运输费用 $w_i$ 和景观评分 $b_i$ 。从城市 $1$ 到城市 $n$ ，可以免除路径上景观评分最高的一条边的运输费用；若最高评分边有多条，只免除其中一条。求最小运输费用；若无法到达，输出 $\text{-1}$ 。

解题思路

枚举路径中最高景观评分为 $B$ 。

此时路径只能使用：

b_i\le B

的边，并且必须至少使用一条：

b_i=B

的边作为免费边。

对每个不同的 $B$ ，跑一个二层 $\text{Dijkstra}$ ：

状态 $0$ ：还没有使用免费边；
状态 $1$ ：已经使用了免费边。

转移：

所有 $b_i\le B$ 的边都可以正常付费通过；
如果当前还没使用免费边，并且这条边满足 $b_i=B$ ，可以免费通过一次并进入状态 $1$ 。

最终取所有 $B$ 下到达 $(n,1)$ 的最小值。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Edge {
    int to;
    LL w, b;
};
struct Node {
    LL d;
    int u, s;
    bool operator < (const Node &o) const {
        return d > o.d;
    }
};
int n, m;
vector<Edge> g[5010];
vector<LL> bs;
LL dis[2][5010];
LL dij(LL B) {
    for (int i = 1; i <= n; i++) dis[0][i] = dis[1][i] = inf;
    priority_queue<Node> q;
    dis[0][1] = 0;
    q.push({0, 1, 0});
    while (!q.empty()) {
        Node cur = q.top(); q.pop();
        LL d = cur.d;
        int u = cur.u, s = cur.s;
        if (d != dis[s][u]) continue;
        for (auto e : g[u]) {
            if (e.b > B) continue;
            if (dis[s][e.to] > d + e.w) {
                dis[s][e.to] = d + e.w;
                q.push({dis[s][e.to], e.to, s});
            }
            if (s == 0 && e.b == B) {
                if (dis[1][e.to] > d) {
                    dis[1][e.to] = d;
                    q.push({dis[1][e.to], e.to, 1});
                }
            }
        }
    }
    return dis[1][n];
}
inline void solve() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        LL w, b;
        cin >> u >> v >> w >> b;
        g[u].push_back({v, w, b});
        g[v].push_back({u, w, b});
        bs.push_back(b);
    }
    sort(bs.begin(), bs.end());
    bs.erase(unique(bs.begin(), bs.end()), bs.end());
    LL Ans = inf;
    for (LL B : bs) Ans = min(Ans, dij(B));
    if (Ans == inf) printf("-1\n");
    else printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}