UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185137#2680. Travel29511544801001585ms5180kbC++11986b2023-09-23 09:45:062023-09-23 12:10:14

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
int n,m,l,f[505][505],g[505][505];
inline void init(){
	memset(g,0x3f,sizeof(g));
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(f[i][j]<=l) g[i][j]=g[j][i]=1;
		}
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
			}
		}
	}
}
signed main()
{
	int T;
	memset(f,0x3f,sizeof(f));
	scanf("%lld%lld%lld",&n,&m,&l);
	for(int i=1;i<=n;i++) f[i][i]=g[i][i]=0;
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		if(u==v) continue;
		f[u][v]=f[v][u]=min(f[u][v],w);
	}
	init();
	scanf("%lld",&T);
	while(T--){
		int u,v;
		scanf("%lld%lld",&u,&v);
		if(g[u][v]>1e7) puts("-1");
		else printf("%lld\n",g[u][v]-1);
	}
	return 0;
}

详细

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

Test #1:

score: 5
Accepted
time: 84ms
memory: 5172kb

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: 5
Accepted
time: 74ms
memory: 5180kb

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
-1
3
-1
5
2
3
2
2
1
0
3
4
2
3
2
2
3
3
3
4
3
5
3
3
4
-1
4
4
3
4
1
3...

result:

ok 89700 lines

Test #3:

score: 5
Accepted
time: 80ms
memory: 5176kb

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: 84ms
memory: 5172kb

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: 79ms
memory: 5172kb

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: 5
Accepted
time: 75ms
memory: 5180kb

input:

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

output:

-1
-1
-1
-1
-1
10
-1
11
-1
11
7
9
-1
9
6
7
8
-1
-1
4
-1
10
5
7
-1
-1
11
4
6
-1
-1
5
4
1
-1
-1
-1
-1
...

result:

ok 89700 lines

Test #7:

score: 5
Accepted
time: 80ms
memory: 5176kb

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: 78ms
memory: 5172kb

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: 5172kb

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: 78ms
memory: 5176kb

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: 78ms
memory: 5172kb

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: 82ms
memory: 5176kb

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: 82ms
memory: 5176kb

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: 80ms
memory: 5176kb

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: 81ms
memory: 5172kb

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: 78ms
memory: 5176kb

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: 78ms
memory: 5176kb

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: 5
Accepted
time: 77ms
memory: 5176kb

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
-1
-1
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
1
2
3
-1
4
4
4
-...

result:

ok 89700 lines

Test #19:

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

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: 5
Accepted
time: 82ms
memory: 5180kb

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:

ok 89700 lines