CCF GESP 2026年3月认证 C++ 7级
题目描述
小 A 想将正整数 n 拆分成若干个正整数之和，并最大化拆分后的正整数之积。小 A 希望你帮他计算出拆分后正整数之积的最大值。由于答案可能很大，你只需要求出答案对 $10^9$ 取模的结果。
形式化地，n 的拆分是满足 $a_1+⋯+a_k=n$ 的若干个正整数 $a_1,…,a_k$，其中 1≤k≤n。你需要求出 n 的所有拆分中 $a_1×⋯×a_n$ 的最大值对 $10^9$ 取模的结果。
输入格式
第一行，一个正整数 t，表示数据组数。
对于每组数据：一行，一个整数 n，表示给定的正整数。
输出格式
对于每组数据：输出一行，一个整数，表示 n 拆分后正整数之积的最大值对 $10^9$ 取模的结果。
样例说明
样例 1
3
5
8
1006
18
755407364数据范围
对于 40% 的测试点，保证 n≤50。
对于所有测试点，保证 $1≤t≤10^4，1≤n≤10^6$。
题目描述
一个物流网络由 n 个城市和 m 条双向公路组成。每条公路都有两个属性：
- 运输费用 $w_i$
- 景观评分 $b_i$
当一辆运输车从城市 1 运送货物到城市 n 时，需要支付经过道路的运输费用之和。
为了推广旅游线路，物流公司推出了一项优惠政策：在运输路径上，可以免除景观评分最高的那条公路的运输费用。如果有多条公路的景观评分同为最大值，则只免除其中 一条 的费用。
请你计算，从城市 1 到城市 n 的最小运输费用。
输入格式
第一行两个整数 n,m，分别表示城市数量和公路数量。
接下来 m 行，每行四个整数 u,v,w,b，表示存在一条连接城市 u 和城市 v 的双向公路，其中 w 为运输费用，b 为景观评分。
输出格式
输出一个整数，表示从城市 1 到城市 n 的最小费用。
如果无法到达，输出 -1。
样例说明
样例 1
3 3
1 2 10 5
2 3 20 6
1 3 100 10路径 1→2→3：费用 10+20，最大美丽值 6（边 2−3）。免除 20，总花费 10。
路径 1→3：费用 100，最大美丽值 1（边 1−3）。免除 100，总花费 0。
最小费用为0。
数据范围
$1≤n≤5000，1≤m≤5000，1≤w,b≤10^9$。