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://pwwzsj.com/article/dochji.html