资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

C++题目大总结（持续更新中）-创新互联

文章目录
  • S
    • 搜索
      • 1.城市距离（ 普 及 + / 提 高 \textcolor{green}{普及+/提高} 普及+/提高）
    • 数位DP
      • 1.手机号码（CQOI2016，, 省 选 / N O I − \textcolor{purple}{省选/NOI-} 省选/NOI−）
    • 思维/数学
      • 1.I Hate 1111(CF1526B, 普 及 / 提 高 − \textcolor{yellow}{普及/提高-} 普及/提高−)
  • Z
    • 状压DP
      • 1.Marbles(CF1215E, 提 高 + / 省 选 − \textcolor{blue}{提高+/省选-} 提高+/省选−)
    • 最短路
      • 1.逛公园（NOIP2017 提高组, 省 选 / N O I − \textcolor{purple}{省选/NOI-} 省选/NOI−）

备注：题目后的难度评价是这样制定的
1.若 l u o g u luogu luogu 上有难度评价（除 暂无评价 外），则为 l u o g u luogu luogu 上的难度评价。
2.否则，作者将参考其他类似题目的难度评价与个人主观来评价其难度。

成都创新互联专注于企业成都全网营销推广、网站重做改版、蒙阴网站定制设计、自适应品牌网站建设、H5建站、成都商城网站开发、集团公司官网建设、外贸网站制作、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为蒙阴等各大城市提供网站开发制作服务。S 搜索 1.城市距离（ 普 及 + / 提 高 \textcolor{green}{普及+/提高} 普及+/提高）

U p d Upd Upd： 2022.11.28 2022.11.28 2022.11.28 完成
八中OJ链接
我们还是先观察数据范围： 1 ≤ n , m ≤ 500 1 \leq n,m \leq 500 1≤n,m≤500,那么就只能用广度优先搜索了。
个人认为这道题出得不好，因为按照目前的最优解，时间复杂度应该为 O ( n 2 m 2 ) O(n^2m^2) O(n2m2) 的，应该是过不掉的，但为什么在 150 m s 150ms 150ms 内就过掉了呢？原因有二：一是数据太水，仅有一组极限数据并且 ‘#’ 符号少得可怜。二是如果每一次 b f s bfs bfs 不用 O ( n m ) O(nm) O(nm) 的时间初始化，其实真正的时间复杂度是远远小于 O ( n 2 m 2 ) O(n^2m^2) O(n2m2) 的。
我们先来想一想最暴力的做法，枚举两个城市，再用 O ( n m ) O(nm) O(nm) 求其最短距离，这样做是 O ( n 3 m 3 ) O(n^3m^3) O(n3m3) 的，绝对会原地起飞。
现在，来说说这道题的正确做法——染色法，即将每个城市用 d f s dfs dfs 染色后去求解。如果每个城市只有一个 #，那么，这个问题就是一个很裸的 B F S BFS BFS 问题。但是，现在的问题就是，要如何
做，才能够求得一片城市与另一片城市的最短距离？其实，每一次 b f s bfs bfs 最坏会遍历整个地图，并且我们只是求其最小距离，所以，我们可以将某一个城市内的所有 # 全都作为我们搜索的起点，然后计算从这些起点当中，走到另一个 # 的最短距离是多少（ B F S BFS BFS），因为我们只需要找到最小距离，并不需要知道究竟是哪个城市到了另外哪个城市，因此，我们在跑 B F S BFS BFS 之前，找到当前我们找的这个城市有哪些 #，将同一个城市内的所有#都 p u s h push push 进我们的队列当中，然后，再跑一个 B F S BFS BFS，找到这个城市能走到的离它最近的城市的距离，最后取最小的那个答案即可。
A C AC AC C o d e : Code: Code:

#includeusing namespace std;
const int N = 5e2 + 5, INF = 0x3f3f3f3f;
const int zx[4] = {-1, 0, 1, 0}, zy[4] = {0, 1, 0, -1};
int n, m, ans = INF;
char c[N][N];
bool vis[N][N];
struct node {int x, y, step;
};
queueq;
bool in(int x, int y) {return x >= 1 && x<= n && y >= 1 && y<= m;
}
void dfs(int x, int y) {c[x][y] = 'A';
	q.push((node){x, y, 0});
	for(int i = 0;i< 4;i++) {int dx = x + zx[i], dy = y + zy[i];
		if(in(dx, dy) && c[dx][dy] == '#') dfs(dx, dy);
	}
}
void bfs() {for (int i = 1;i<= n;i++)
		for (int j = 1;j<= m;j++)
			vis[i][j] = 0;
	while(!q.empty()) {node p = q.front();
		q.pop();
		if(c[p.x][p.y] == '#') {	while(!q.empty()) q.pop();
			ans = min(ans, p.step);
			return ;
		}
		for(int i = 0;i< 4; ++i) {	int dx = p.x + zx[i], dy = p.y + zy[i];
			if(in(dx, dy) && !vis[dx][dy] && c[dx][dy] != 'A') {		vis[dx][dy] = 1;
				q.push((node){dx, dy, p.step + 1});
			}
		}
	}
}
int main() {scanf("%d%d", &n, &m);
	for(int i = 1;i<= n;i++) scanf("%s", c[i] + 1);
	for(int i = 1;i<= n;i++)
		for(int j = 1;j<= m;j++)
			if(c[i][j] == '#') {		dfs(i, j);
				bfs();
			}
	printf("%d", ans);
	return 0;
}
数位DP 1.手机号码（CQOI2016，, 省 选 / N O I − \textcolor{purple}{省选/NOI-} 省选/NOI−）

U p d Upd Upd： 2022.11.26 2022.11.26 2022.11.26 完成
洛谷链接 八中OJ链接
看到数据范围 1 0 10 ≤ L ≤ R ≤ 1 0 11 10^{10} \leq L \leq R \leq 10^{11} 1010≤L≤R≤1011 并且是统计 [ L , R ] [L,R] [L,R] 内有满足条件的号码数量，很容易想到数位 D P DP DP。
其实，数位 D P DP DP 也是一个很模板化的东西。对其总结如下：

dfs(数的最后若干位,各种限制条件,当前第几位)
	if 最后一位
    	return 各种限制条件下的返回值
    局部变量 ct = 当前位的数字
    局部变量 sum = 0;
    for i = 0 to ct - 1
    	sum += 当前位取i时一定无无限制的合法状态数
        sum += 当前位取i时满足当前限制的合法状态数
    根据ct更新限制条件 不再满足则 return sum
    return sum + dfs(当前位后的若干位,更新后的限制条件,下一位)

slv(当前数)
	if (只有一位) return 对应的贡献
    局部变量 ct;
    for ct = 可能最高位 to 1
    	if 当前位有数字 break
    局部变量 nw = 当前位数字
    局部变量 sum = 0
    for i = 1 to nw - 1
    	sum += 当前位取i后合法情况任意取的贡献
    for i = 1 to ct-1
    	for j = 1 to 9
        	sum +=  第i位取j后合法情况任意取的贡献
    sum += dfs(去掉第一位后的若干位,限制条件,第二位)
    return sum

main
	预处理当前位取i的各种条件各种限制的贡献
    读入 L R
    --L
    输出 slv(R)-slv(L)
    return 0

而在这道题中，我们就可以很容易的套模板，定义六维的 D P DP DP 去记忆化 d f s dfs dfs,即 d p [ 第 i 位 ] [ 填 j ] [ 目 前 连 续 L ] [ 是 否 有 4 ] [ 是 否 有 8 ] [ 是 否 有 至 少 3 位 连 续 数 字 ] dp[第i位][填j][目前连续L][是否有4][是否有8][是否有至少3位连续数字] dp[第i位][填j][目前连续L][是否有4][是否有8][是否有至少3位连续数字]。
然后按照板子按部就班的做便能 A C AC AC.
A C AC AC C o d e Code Code:

#includeusing namespace std;
#define int long long
const int N = 20;
int x, y, num[N], dp[N][N][N][2][2][2];
int dfs(int pos, int pre1, int pre2, bool limit, bool zero, bool e, bool f, bool ok) {if (e && f) return 0;
    if (!pos) return ok;
    if (!limit && !zero && dp[pos][pre1][pre2][e][f][ok]) return dp[pos][pre1][pre2][e][f][ok];
    int mxd = limit ? num[pos] : 9;
    int ans = 0;
    for (int i = 0; i<= mxd;i++)
        ans += dfs(pos - 1, (zero && !i) ? -1 : i, zero ? -1 : pre1, limit && i == mxd, zero && !i, e || i == 8, f || i == 4, ok || ((!zero && i == pre1 && i == pre2)));
    if (!limit && !zero) dp[pos][pre1][pre2][e][f][ok] = ans;
    return ans;
}
int solve(int x) {int len = 0;
    while (x) num[++len] = x % 10, x /= 10;
    return dfs(len, -1, -1, 1, 1, 0, 0, 0);
}
signed main() {scanf("%lld%lld", &x, &y);
	printf("%lld", solve(y) - solve(x - 1));
    return 0;
}
思维/数学 1.I Hate 1111(CF1526B, 普 及 / 提 高 − \textcolor{yellow}{普及/提高-} 普及/提高−)

U p d Upd Upd： 2022.11.26 2022.11.26 2022.11.26 完成
洛谷链接
解题思路：由数据范围 1 ≤ x ≤ 1 0 9 1 \leq x \leq 10^9 1≤x≤109 可得，这是一道思维题。
思维题，其实无非分为以下四种：拼凑、归纳、分类、数论。
而这一题，题中没有复杂的数学公式，便可以从拼凑角度出发。
随便列举出一些数字：
122 = 111 ∗ 1 + 11 ∗ 1 122 = 111 * 1 + 11 * 1 122=111∗1+11∗1, 233 − 111 ∗ 2 + 11 ∗ 1 233 - 111 * 2 + 11 * 1 233−111∗2+11∗1
发现，似乎三位数可以由 11 11 11 和 111 111 111 拼凑，那么更高位数字呢？。
我们又可以发现：
11 − > 11 11 ->11 11−>11
111 − > 111 111 ->111 111−>111
1111 − > 11 × 100 + 11 1111 ->11 \times 100 + 11 1111−>11×100+11
11111 − > 11 × 1000 + 111 11111 ->11 \times 1000 + 111 11111−>11×1000+111
111111 − > 1111 × 10 + 11 − > 11 × 1000 + 1111 111111 ->1111 \times 10 + 11 ->11 \times 1000 + 1111 111111−>1111×10+11−>11×1000+1111
又因为 111 = 11 × 10 + 1 111 = 11 \times 10 + 1 111=11×10+1
所以 11 x + 111 y = 11 （ x + 10 y ） + 1 11x + 111y = 11（x + 10y）+1 11x+111y=11（x+10y）+1
此时，我们就可以求解出 x 、 y x、y x、y 的值。
我们还可以发现这些数的一个美好特征：永远可以将一个非常大的数字消到三位数以下，也就说我们可以分段打表（有人 A C AC AC 过）求出 x % 11 × 111 x \% 11 \times 111 x%11×111 后判断是否小于 x x x 即可。
A C AC AC C o d e Code Code:

#includeusing namespace std;
#define int long long
int T, x;
signed main() {scanf("%lld", &T);
    while(T--) {scanf("%lld", &x);
        if (x % 11 * 111<= x) puts("YES");
        else puts("NO");
    }
    return 0;
}
//num = 11 * x + 111 * y
//num = 11 * (x + 10 * y) + y
Z 状压DP 1.Marbles(CF1215E, 提 高 + / 省 选 − \textcolor{blue}{提高+/省选-} 提高+/省选−)

U p d Upd Upd： 2022.11.26 2022.11.26 2022.11.26 完成
八中OJ链接 洛谷链接
可以观察数据范围 1 ≤ a i ≤ 20 1 \leq a_i \leq 20 1≤ai​≤20,可以用状压 D P DP DP 求解。
细看题目，便发现有这样一个性质：如果交换相邻的两数，其他所有数字的相对位置是不变的。（其实，也可以根据逆序对的一个引理得出：将一个序列排序最少交换相邻元素的次数等于该序列的逆序对数。）
推论：在交换的时候我们就可以分开考虑每一种数字。

例如: 1 1 1 1 1 1 3 3 3 2 2 2 4 4 4 中,我们发现交换下标为 1 1 1 和 2 2 2 的数字，其实序列并没有改变，而颜色只有 20 20 20 种,也就是相邻的同种颜色不考虑交换。
于是，我们可以来状压颜色的种类。
D P DP DP 的定义如下：定义 d p i dp_i dpi​ 表示表示已选的数的状态集合（注意，每选择一个数，意味着给其赋一个比之前选的数都大，比之后选的数都小的权值），集合中的数权值逆序对的最小值。
理解一下：若有一个序列 1 1 1 2 2 2 1 1 1 3 3 3, d p [ 3 ] = d p [ ( 011 ) 2 ] dp[3] = dp[(011)_2] dp[3]=dp[(011)2​] (已经选择了 1 1 1 和 2 2 2 两种数) = 1 =1 =1.为什么呢？因为既然是求权值逆序对，即我们可以将它同种类数字赋上同一个值，求其值逆序对的最小值。在这里，我们将 1 1 1 赋值为 1 1 1, 2 2 2 赋值为 2 2 2,便会有一个逆序对，就是最小值。
接着，我们来考虑一下转移方程吧。 d p i dp_i dpi​ 应该怎么转移呢？
当我们在更新状态 i i i 时， i i i 以前 d p dp dp 值应该是有的，那么，我们可以枚举颜色的种类，假设没有这个种类的数字的 d p dp dp 值加上 v a l val val ( v a l val val 就是逆序对个数)，即 d p i = m i n ( d p i , d p j + v a l ) dp_i = min(dp_i,dp_j+val) dpi​=min(dpi​,dpj​+val)
而这个 v a l val val 的值需要用两重循环去枚举，会 T T T！怎么办？可以用一个数组预处理。用 c x y c_{xy} cxy​ 表示数列中满足 i ＜ j i ＜ j i＜j 且 a i = x a_i = x ai​=x, a j = y a_j = y aj​=y 的 ( i , j ) (i,j) (i,j) 对数。
这样，这道状压 D P DP DP 的题目就可以被解决了，最坏时间复杂度为 O （ 4 ∗ 1 0 5 × 20 + 2 20 × 2 0 2 ） O（4*10^5 \times 20 + 2^{20} \times 20^2） O（4∗105×20+220×202） 运算次数约为 4 ∗ 1 0 7 4*10^7 4∗107,时限 4 s e c 4 sec 4sec，可以通过。
但是，注意一点，初始化 D P DP DP 时候，不能只初始化到 1 < < m a x n 1<< maxn 1< W A WA WA 60 60 60 C o d e Code Code

#includeusing namespace std;
#define int long long
const int N = 4e5 + 5, M = 25, INF = 0x3f3f3f3f;
int n, maxx, maxn, a[N], cnt[M], c[M][M], dp[(1<< 20) + 5];
signed main() {scanf("%lld", &n);
    for (int i = 1;i<= n;i++) scanf("%lld", &a[i]), a[i]--;
    maxx = *max_element(a + 1, a + n + 1) + 1, maxn = (1<< maxx) - 1;
    for (int i = 1;i<= n;i++) {cnt[a[i]]++;
    	for (int j = 0;j<= maxx;j++) c[j][a[i]] += cnt[j];
	}
	for (int i = 1;i<= maxn;i++) dp[i] = INF;
	for (int i = 1;i<= maxn;i++)
		for (int j = 0;j< maxx;j++)
			if (i & (1<< j)) {		int val = 0, pre = i - (1<< j);
				for (int k = 0;k< maxx;k++) if (pre & (1<< k)) val += c[j][k];
				dp[i] = min(dp[i], dp[pre] + val);
			}
	printf("%lld", dp[maxn]);
    return 0;
}

A C AC AC C o d e Code Code

#includeusing namespace std;
#define int long long
const int N = 4e5 + 5, M = 25, INF = 0x3f3f3f3f;
int n, maxx, maxn, a[N], cnt[M], c[M][M], dp[(1<< 20) + 5];
signed main() {scanf("%lld", &n);
    for (int i = 1;i<= n;i++) scanf("%lld", &a[i]), a[i]--;
    maxx = *max_element(a + 1, a + n + 1) + 1, maxn = (1<< maxx) - 1;
    for (int i = 1;i<= n;i++) {cnt[a[i]]++;
    	for (int j = 0;j<= maxx;j++) c[j][a[i]] += cnt[j];
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	for (int i = 1;i<= maxn;i++)
		for (int j = 0;j< maxx;j++)
			if (i & (1<< j)) {		int val = 0, pre = min(i - (1<< j), maxn + 1);
				for (int k = 0;k< maxx;k++) if (pre & (1<< k)) val += c[j][k];
				dp[i] = min(dp[i], dp[pre] + val);
			}
	printf("%lld", dp[maxn]);
    return 0;
}
最短路 1.逛公园（NOIP2017 提高组, 省 选 / N O I − \textcolor{purple}{省选/NOI-} 省选/NOI−）

U p d Upd Upd： 2022.11.26 2022.11.26 2022.11.26 完成
八中OJ链接 洛谷链接

首先，我们要知道 1 − n 1-n 1−n 的最短路的距离是多少。于是我们可以跑一遍 d i j k s t r a dijkstra dijkstra 来 O ( n l o g n ) O(n log n) O(nlogn) 求最短距离。
然后我们可以发现 0 ≤ k ≤ 50 0 \leq k \leq 50 0≤k≤50 ，于是我们可以在 k k k 上面做一个 D P DP DP。
不难定义出 d p u d dp_{ud} dpud​ 表示路程为区间 [ d i s u , d i s u + d ] [dis_u, dis_u+d] [disu​,disu​+d] 以内的方案数（ d i s u dis_u disu​ 表示到 u u u 的最短路)
于是我们可以在每种询问时暴力枚举 k k k ，每次用 d f s dfs dfs 记忆化的方式来计算 d p n i dp_{ni} dpni​ 的值，答案即为 d p n i dp_{ni} dpni​ 之和。
那么 d f s dfs dfs 应该怎么写呢？
对于每一个 d f s dfs dfs ，我们可以枚举起点（可以反向建图，将终点作为起点）能到达的点，我们就可以由 d f s ( u , l ) dfs(u,l) dfs(u,l) 转到 d f s ( v , d i s [ u ] + l − d i s [ v ] − e d g e 2 [ i ] . l e n ) dfs(v,dis[u]+l-dis[v]-edge2[i].len) dfs(v,dis[u]+l−dis[v]−edge2[i].len)了。
边界便为当 i ≤ − 1 i \leq -1 i≤−1 或 i ≠ k + 1 i \neq k + 1 i​=k+1时，返回 0 0 0;
但是，数据中有明显的指示，有 0 0 0 边！所以我们可以用一个 f l a g flag flag 数组来标记。
最后，我们可以将这个 d f s dfs dfs 记忆化，每个点和边在一个 d f s dfs dfs 最多只会遍历一次，所以时间复杂度为 O ( n O(n O(n l o g ( n + m ) + k ( n + m ) ) log(n+m)+k(n+m)) log(n+m)+k(n+m))。
A C AC AC C o d e 1 Code1 Code1:

#includeusing namespace std;
const int N = 2e5 + 1, M = 51;
struct node{int val, dis;
	friend bool operator< (node x, node y) {return x.dis >y.dis;}
};
priority_queueq;
struct Edge{int to, next, len;
}edge[N<< 1], edge2[N<< 1];
int T, n, m, K, P, num, num2, head[N], head2[N], dis[N], vis[N], flag[N][M], dp[N][M];
void add(int x, int y, int z) {edge[++num] = (Edge){y, head[x], z}, head[x] = num; }
void adds(int x, int y, int z) {edge2[++num2] = (Edge){y, head2[x], z}, head2[x] = num2; }
void Dijkstra() {for (int i = 1; i<= n; ++i) vis[i] = 0, dis[i] = 1e9; dis[1] = 0;
	q.push((node){1, 0});
	while (!q.empty()){node tmp = q.top(); q.pop();
		int u = tmp.val, l = tmp.dis;
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = head[u]; i; i = edge[i].next){	int v = edge[i].to;
			if (dis[v] >dis[u] + edge[i].len){		dis[v] = dis[u] + edge[i].len;
				if (!vis[v]) q.push((node){v, dis[v]});
			}
		}
	}
}
int dfs(int u, int l) {if (l< 0 || l >K) return 0;
	if (flag[u][l]) return -1;
	if (dp[u][l] != -1) return dp[u][l];
	flag[u][l] = 1;
	int sum = 0;
	for (int i = head2[u]; i; i = edge2[i].next){int v = edge2[i].to;
		int tmp = dfs(v, dis[u] + l - dis[v] - edge2[i].len);
		if (tmp == -1) return -1;
		(sum += tmp) %= P;
	}
	if (u == 1 && !l) ++sum;
	dp[u][l] = sum, flag[u][l] = 0;
	return sum;
}
int main() {scanf("%d", &T);
	while (T--) {num = num2 = 0;
		memset(head, 0, sizeof(head));
		memset(head2, 0, sizeof(head2));
		scanf("%d%d%d%d", &n, &m, &K, &P);
		for (int i = 1, x, y, z;i<= m;i++) {	scanf("%d%d%d", &x, &y, &z);
			add(x, y, z), adds(y, x, z);
		}
		Dijkstra();
		memset(dp, 255, sizeof(dp));
		memset(flag, 0, sizeof(flag));
		int ans = 0, flag = 0;
		for (int i = 0; i<= K;i++) {	int tmp = dfs(n, i);
			if (tmp == -1){flag = 1; break;}
			ans = (ans + tmp) % P;
		}
		if (!flag) printf("%d\n", ans);
		else puts("-1");
	}
	return 0;
}

下面便是用 T o p S o r t TopSort TopSort 的做法，复杂度相同(别人的)（其实是 d f s dfs dfs 的作用）。
另外， S t r u c t Struct Struct 的封装也很好。
A C AC AC C o d e 2 Code2 Code2:

#includeconst int N = 1e5 + 10, M = 2e5 + 10, Nt = 131072, inf = 0x3f3f3f3f;
int ri() {char c = getchar(); int x = 0, f = 1; for(;c< '0' || c >'9'; c = getchar()) if(c == '-') f = -1;
	for(;c >= '0' && c<= '9'; c = getchar()) x = (x<< 1) + (x<< 3) - '0' + c; return x * f;
}
int n, q[N], d[N], rk[N], f[N], g[N], *D, id[N], T[Nt<< 1], dp[51][N], K, P;
struct Edge {int nx[M], pr[N], to[M], w[M], tp;
	void add(int u, int v, int W) {to[++tp] = v; nx[tp] = pr[u]; pr[u] = tp; w[tp] = W;}
	void adds(int u, int v, int w) {add(u, v, w); add(v, u, w);}
	void Pre() {for(int i = 1;i<= n; ++i) pr[i] = 0; tp = 0;}
}G, R;
int min(int a, int b) {return D[a]< D[b] ? a : b;}
bool cmp(int a, int b) {return f[a] == f[b] ? rk[a]< rk[b] : f[a]< f[b];}
void Up(int i, int v) {for(T[i += Nt] = v;i >>= 1;) T[i] = min(T[i<< 1], T[i<< 1 | 1]);}
void Dij(const Edge &G, int st) {for(int i = 0;i<= n; ++i) D[i] = inf;
	D[st] = 0; Up(st, st);
	for(;D[T[1]] != inf;) {int u = T[1]; Up(u, 0);
		for(int i = G.pr[u], v, w; i; i = G.nx[i])
			if(D[v = G.to[i]] >(w = D[u] + G.w[i]))
				D[v] = w, Up(v, v);
	}
}
bool Topsort() {int L = 1, R = 0;
	for(int i = 1;i<= n; ++i) 
		if(!d[i]) 
			q[++R] = i;
	for(int u = q[L];L<= R; u = q[++L])
		for(int i = G.pr[u]; i; i = G.nx[i])
			if(!G.w[i] && !--d[G.to[i]]) 
				q[++R] = G.to[i];
	for(int i = 1;i<= R; ++i) 
		rk[q[i]] = i;
	for(int i = 1;i<= n; ++i)
		if(d[i] && f[i] + g[i]<= f[n] + K)
			return false;
	for(int i = 1;i<= n; ++i) 
		id[i] = i;
	std::sort(id + 1, id + n + 1, cmp);
	return true;
}
void Inc(int &a, int b) {a += b; if(a >= P) a -= P;}
void Dp() {memset(dp, 0, sizeof(dp));
	dp[0][id[1]] = 1;
	for(int k = 0;k<= K; ++k)
		for(int x = 1, u = id[1];x<= n; u = id[++x]) 
			for(int i = G.pr[u], w, v; i; i = G.nx[i]) 
				if((w = f[u] + k + G.w[i] - f[v = G.to[i]])<= K)
					Inc(dp[w][v], dp[k][u]);
}
int main() {for(int C = ri();C--;) {n = ri(); int m = ri(); K = ri(), P = ri();
		G.Pre(); R.Pre();
		for(int i = 1;i<= n; ++i) 
			d[i] = rk[i] = 0;
		for(int u, v, w;m--;) 
			u = ri(), v = ri(), w = ri(), 
			G.add(u, v, w), R.add(v, u, w), d[v] += !w;
		D = f; Dij(G, 1); 
		D = g; Dij(R, n);
		if(!Topsort()) {	puts("-1"); continue;
		}
		Dp();
		int r = 0;
		for(int i = 0;i<= K; ++i) Inc(r, dp[i][n]);
		printf("%d\n", r);
	}
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


文章题目：C++题目大总结（持续更新中）-创新互联
网站链接：http://cdkjz.cn/article/dochji.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
重庆服务器托管模板商城网站成都虚拟主机成都网站设计成都帛金建站成都搅拌罐车主机租用成都标志设计网站解决方案微信公众号开发

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图