UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214154#2680. Travellaiyishi801392ms1908kbC++11834b2024-11-15 20:33:122024-11-15 23:26:11

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,l;
int dis1[305][305],dis2[305][305];
int main(){
	scanf("%d%d%d",&n,&m,&l);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis1[i][j]=(i!=j)?0x3fffffff:0;
	while(m--){
		int u,v,w;scanf("%d%d%d",&u,&v,&w);
		dis1[u][v]=dis1[v][u]=min(dis1[u][v],w);
	}
	for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
		dis1[i][j]=min(dis1[i][j],dis1[i][k]+dis1[k][j]);
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis2[i][j]=(i!=j)?0x3fffffff:0;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
		if(dis1[i][j]<=l&&i!=j)dis2[i][j]=1;
	}
	for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
		dis2[i][j]=min(dis2[i][j],dis2[i][k]+dis2[k][j]);
	}
	int q;scanf("%d",&q);
	while(q--){
		int s,t;scanf("%d%d",&s,&t);
		printf("%d\n",dis2[s][t]-1);
	}
}
源文件, 语言: C++11

详细

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

Test #1:

score: 5
Accepted
time: 66ms
memory: 1904kb

input:

300 1031 1000000000
277 94 1000000000
245 178 1000000000
161 263 1000000000
187 73 1000000000
219 36...

output:

3
3
3
2
3
3
2
1
3
2
3
1
1
3
3
2
1
2
2
3
3
2
3
2
2
3
2
2
0
3
1
2
3
2
3
3
2
3
2
3
2
2
3
2
2
2
3
2
3
2
...

result:

ok 89700 lines

Test #2:

score: 0
Wrong Answer
time: 70ms
memory: 1908kb

input:

300 604 1000000000
216 182 1000000000
171 212 1000000000
201 242 1000000000
181 93 1000000000
181 23...

output:

2
3
5
3
3
4
3
5
3
5
5
4
5
4
4
4
3
1073741822
3
1073741822
5
2
3
2
2
1
0
3
4
2
3
2
2
3
3
3
4
3
5
3
3
...

result:

wrong answer 18th lines differ - expected: '-1', found: '1073741822'

Test #3:

score: 5
Accepted
time: 70ms
memory: 1908kb

input:

300 887 1000000000
74 50 1000000000
111 160 1000000000
27 44 1000000000
171 145 1000000000
202 223 1...

output:

3
3
2
2
3
2
2
3
3
2
3
2
2
1
2
2
2
0
1
2
1
2
2
2
2
1
4
0
3
2
2
2
2
3
1
3
3
2
1
3
3
1
1
1
2
2
2
4
2
2
...

result:

ok 89700 lines

Test #4:

score: 5
Accepted
time: 69ms
memory: 1908kb

input:

300 1216 1000000000
272 88 1000000000
186 264 1000000000
132 72 1000000000
203 142 1000000000
126 79...

output:

3
2
2
2
3
3
2
2
2
1
2
2
1
3
3
1
1
2
2
3
1
2
1
1
3
3
1
2
1
3
2
3
1
1
2
2
2
2
2
2
2
3
1
3
2
3
2
3
2
2
...

result:

ok 89700 lines

Test #5:

score: 5
Accepted
time: 66ms
memory: 1908kb

input:

300 1361 1000000000
65 156 1000000000
214 24 1000000000
217 129 1000000000
197 235 1000000000
154 17...

output:

1
1
3
2
2
2
2
2
2
2
1
2
2
3
2
2
2
2
2
1
2
1
2
2
1
1
3
3
2
2
1
0
2
1
2
2
2
1
2
2
2
3
2
2
2
1
3
1
1
2
...

result:

ok 89700 lines

Test #6:

score: 0
Wrong Answer
time: 75ms
memory: 1908kb

input:

300 294 1000000000
167 15 1000000000
21 161 1000000000
250 37 1000000000
32 169 1000000000
60 194 10...

output:

1073741822
1073741822
1073741822
1073741822
1073741822
10
1073741822
11
1073741822
11
7
9
1073741822...

result:

wrong answer 1st lines differ - expected: '-1', found: '1073741822'

Test #7:

score: 5
Accepted
time: 59ms
memory: 1904kb

input:

300 1415 1000000000
215 261 1000000000
208 170 1000000000
191 189 1000000000
103 293 1000000000
215 ...

output:

2
1
2
1
2
2
3
3
2
2
3
2
2
2
1
2
1
2
2
2
2
2
2
3
2
2
1
2
1
2
2
2
2
3
1
2
2
1
2
2
2
2
2
1
2
2
3
2
1
1
...

result:

ok 89700 lines

Test #8:

score: 5
Accepted
time: 71ms
memory: 1904kb

input:

300 1851 1000000000
75 233 1000000000
285 187 1000000000
269 89 1000000000
245 240 1000000000
134 15...

output:

2
2
1
2
2
1
1
1
1
1
1
1
2
3
2
2
2
2
1
2
2
1
2
2
1
1
2
1
2
1
2
2
1
1
1
1
2
2
2
1
2
1
2
1
1
2
1
2
1
1
...

result:

ok 89700 lines

Test #9:

score: 5
Accepted
time: 78ms
memory: 1904kb

input:

300 3491 1000000000
50 182 915397053
64 2 856684642
9 95 764580683
243 83 861656918
89 150 957931575...

output:

0
1
2
0
1
1
0
1
1
1
1
1
2
2
1
1
1
1
2
1
1
1
1
1
1
1
1
1
2
1
1
2
0
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
2
...

result:

ok 89700 lines

Test #10:

score: 5
Accepted
time: 77ms
memory: 1908kb

input:

300 1945 1000000000
47 188 533599055
65 169 659762016
227 218 566867001
31 6 774365594
122 236 88888...

output:

1
1
1
2
3
2
2
1
1
1
2
2
1
0
2
2
2
2
1
0
2
1
1
2
2
2
1
2
2
1
1
1
2
2
2
1
1
1
1
2
2
1
1
1
2
3
2
2
0
2
...

result:

ok 89700 lines

Test #11:

score: 5
Accepted
time: 74ms
memory: 1908kb

input:

300 2334 1000000000
26 91 919619085
219 184 684076993
140 146 629398252
290 115 620714562
183 200 73...

output:

1
1
1
0
2
2
3
1
1
2
0
2
1
2
1
1
1
2
1
2
1
2
1
1
1
2
1
1
2
1
1
1
1
1
2
2
2
1
2
1
1
1
2
2
2
2
1
1
1
2
...

result:

ok 89700 lines

Test #12:

score: 5
Accepted
time: 75ms
memory: 1908kb

input:

300 1783 1000000000
125 59 913425325
201 103 599015877
260 43 836109177
295 13 548588010
289 12 8800...

output:

2
1
1
2
2
1
2
1
2
2
2
2
1
2
2
1
2
0
0
1
2
2
1
1
2
1
2
2
1
2
2
1
1
0
1
1
2
1
2
2
2
2
2
2
2
2
2
2
2
2
...

result:

ok 89700 lines

Test #13:

score: 5
Accepted
time: 67ms
memory: 1908kb

input:

300 2716 1000000000
53 190 602802421
18 208 539008167
159 74 737081869
54 107 984931630
147 117 5946...

output:

1
2
2
1
1
1
1
1
1
1
1
1
2
1
1
2
2
1
2
1
2
1
2
2
2
1
1
2
2
1
1
1
1
2
1
1
1
2
2
1
1
1
2
2
2
1
2
1
2
1
...

result:

ok 89700 lines

Test #14:

score: 5
Accepted
time: 67ms
memory: 1904kb

input:

300 1714 1000000000
120 169 762488498
47 114 721913063
256 146 933043076
109 115 853379190
2 119 623...

output:

1
0
2
2
2
3
1
1
2
2
1
2
2
1
1
1
1
2
2
1
1
2
2
1
1
2
2
1
2
2
2
2
1
1
1
2
2
2
1
2
2
2
1
2
2
2
2
2
2
2
...

result:

ok 89700 lines

Test #15:

score: 5
Accepted
time: 66ms
memory: 1908kb

input:

300 1363 1000000000
112 73 623162757
258 123 797794754
132 144 698032064
177 36 915826033
199 297 92...

output:

2
0
2
0
2
1
2
2
2
2
1
2
3
2
2
3
2
2
3
3
2
1
2
1
1
1
2
1
2
1
2
1
3
2
2
2
2
0
2
2
2
2
1
1
2
2
2
2
3
3
...

result:

ok 89700 lines

Test #16:

score: 5
Accepted
time: 70ms
memory: 1908kb

input:

300 3272 1000000000
138 129 925006622
105 6 708584786
254 96 692737494
293 82 747671739
31 126 53260...

output:

1
1
1
1
1
1
1
1
1
1
2
1
1
1
0
0
1
1
1
2
1
1
1
1
1
1
1
1
1
1
2
1
1
1
2
1
2
1
1
2
1
1
1
1
1
1
1
1
1
1
...

result:

ok 89700 lines

Test #17:

score: 5
Accepted
time: 70ms
memory: 1904kb

input:

300 2173 1000000000
100 231 976052116
281 144 956967155
125 74 633252239
9 129 530570874
206 99 5197...

output:

2
1
2
1
2
2
2
2
2
2
1
2
2
2
1
2
1
1
1
2
2
2
2
1
1
0
2
2
1
2
2
1
1
1
1
1
2
2
2
1
2
2
1
1
1
2
2
1
1
1
...

result:

ok 89700 lines

Test #18:

score: 0
Wrong Answer
time: 67ms
memory: 1904kb

input:

300 435 1000000000
54 113 781774474
276 245 753387176
241 210 611204276
49 27 664064527
261 106 8293...

output:

5
4
4
5
7
1073741822
1073741822
5
3
5
3
6
7
3
3
5
4
4
5
4
5
4
3
2
4
5
4
5
3
5
4
5
5
5
3
6
5
5
3
5
4
...

result:

wrong answer 6th lines differ - expected: '-1', found: '1073741822'

Test #19:

score: 5
Accepted
time: 69ms
memory: 1904kb

input:

300 1226 1000000000
63 220 854868106
174 159 653590287
197 51 532677187
185 108 804016280
284 147 75...

output:

2
2
0
2
1
2
1
2
3
3
1
2
2
2
3
3
2
1
2
1
2
2
3
2
2
1
1
3
2
1
1
1
2
2
2
2
2
2
1
2
2
2
3
1
3
2
1
2
2
3
...

result:

ok 89700 lines

Test #20:

score: 0
Wrong Answer
time: 66ms
memory: 1904kb

input:

300 787 1000000000
285 266 813321760
289 201 623167413
7 76 867785258
155 164 621115697
109 226 5419...

output:

3
1
3
2
3
3
2
3
2
3
2
3
1
4
3
2
2
3
1
3
3
2
2
2
1
2
3
4
2
3
3
3
2
4
2
2
1
2
2
3
3
2
5
4
3
4
3
2
3
3
...

result:

wrong answer 265th lines differ - expected: '-1', found: '1073741822'

中文 English

Server time: 2024-12-02 12:25:22 | 开源项目