UOJ Logo Universal Online Judge

UOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#420943#551. 【UNR #4】校园闲逛xiaoyao109ms1456kbC++11749b2020-08-12 10:55:592020-08-12 14:54:30

answer

#include<bits/stdc++.h>
const int mod=998244353;
int f[10][10][300],cnt[10][10][300],n,m,q,maxv;
struct edge { int u,c,t; };
std::vector<edge> G[10];
signed main()
{
	scanf("%d%d%d%d",&n,&m,&q,&maxv);
	for ( int i=1,u,v,c;i<=m;i++ ) scanf("%d%d%d",&u,&v,&c),cnt[u][v][c]++;
	for ( int i=1;i<=maxv;i++ ) for ( int s=1;s<=n;s++ ) for ( int t=1;t<=n;t++ ) if ( cnt[s][t][i] ) G[t].push_back((edge){s,i,cnt[s][t][i]});
	for ( int i=1;i<=n;i++ ) f[i][i][0]=1;
	for ( int i=1;i<=maxv;i++ ) for ( int s=1;s<=n;s++ ) for ( int t=1;t<=n;t++ ) for ( edge E:G[t] )
	{
		if ( E.c>i ) break;
		f[s][t][i]=(f[s][t][i]+1LL*f[s][E.u][i-E.c]*E.t)%mod;
	}
	while ( q-- ) { int u,v,c;scanf("%d%d%d",&u,&v,&c);printf("%d\n",f[u][v][c]); }
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 9ms
memory: 1456kb

input:

8 1988 9994 199
8 3 110
5 1 141
6 8 64
6 8 112
7 6 43
5 2 188
5 7 106
4 1 1
3 5 107
2 4 126
4 2 93
2...

output:

693280711
103779732
305629139
4769
560605439
165519499
33524289
119909482
3272028
115
810426057
0
89...

result:

ok 9994 tokens

Test #2:

score: 0
Runtime Error

input:

1 298540 9960 64989
1 1 44073
1 1 50148
1 1 62314
1 1 58582
1 1 31021
1 1 51585
1 1 6374
1 1 15044
1...

output:


result:


Test #3:

score: 0
Runtime Error

input:

2 297174 9832 64486
2 2 50259
1 1 17559
1 1 55330
2 2 20721
1 1 4820
1 1 45383
1 1 58790
2 1 51083
2...

output:


result:


Test #4:

score: 0
Runtime Error

input:

3 299294 9932 64431
2 2 52965
3 3 55481
3 3 59980
2 3 33535
3 1 27054
1 2 52687
1 3 15680
1 3 52803
...

output:


result:


Test #5:

score: 0
Runtime Error

input:

5 298892 9799 64862
1 4 51738
3 2 51865
3 1 53904
4 1 30693
5 5 27135
4 4 10961
3 1 53498
3 4 28068
...

output:


result:


Test #6:

score: 0
Runtime Error

input:

5 299474 9819 64999
3 1 54445
1 2 52047
3 4 63825
5 5 719
1 1 32869
1 3 33275
5 5 29905
1 4 42797
5 ...

output:


result:


Test #7:

score: 0
Runtime Error

input:

6 299214 9970 64793
2 6 9200
1 1 48687
3 4 49603
6 5 40185
2 5 35590
1 5 29761
5 6 36597
4 1 50585
5...

output:


result:


Test #8:

score: 0
Runtime Error

input:

7 297219 9890 64830
5 6 13865
7 5 12076
6 6 32678
4 5 53494
6 3 42498
6 4 30914
2 2 57146
1 1 51330
...

output:


result:


Test #9:

score: 0
Runtime Error

input:

8 297863 9822 64535
3 6 60844
3 1 60740
1 2 26027
3 2 13707
5 6 19483
2 2 59156
6 6 26271
4 3 37396
...

output:


result:


Test #10:

score: 0
Runtime Error

input:

8 299897 9774 64710
2 7 39644
7 2 59681
6 4 26171
7 7 59221
7 7 43473
6 3 4755
6 6 42609
4 2 36480
7...

output:


result: