UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185129#2680. Travelsnow_trace1003580ms1920kbC++111.0kb2023-09-23 08:36:372023-09-23 12:09:15

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dis[305][305];
int n,m,l;
signed main(){
	cin >> n>> m >> l;
	memset(dis,63,sizeof(dis));
	for(int i = 1;i<=n;i++)dis[i][i] = 0;
	for(int i = 1;i<=m;i++){
		int a,b,c;cin >> a >> b >> c;
		dis[a][b] = min(dis[a][b],c),dis[b][a] = min(dis[b][a],c);
	}for(int k = 1;k<=n;k++){
		for(int i = 1;i<=n;i++){
			if(i == k)continue;
			for(int j = 1;j<=n;j++){
				if(i == j or j == k)continue;
				dis[i][j] = min(dis[i][k]+dis[j][k],dis[i][j]);
			}
		}
	}for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++){
			if(i == j)continue;
			if(dis[i][j]<=l)dis[i][j] = 1;
			else dis[i][j] = 2000000005;
		}
	}for(int k = 1;k<=n;k++){
		for(int i = 1;i<=n;i++){
			if(i == k)continue;
			for(int j = 1;j<=n;j++){
				if(i == j or j == k)continue;
				dis[i][j] = min(dis[i][k]+dis[j][k],dis[i][j]);
			}
		}
	}int q;cin >>q;
	while(q--){
		int a,b;cin >> a >> b;
		if(dis[a][b]>=2000000000){
			cout << -1 << '\n';
		}else cout << dis[a][b]-1 << '\n';
	}
	return 0;
}
源文件, 语言: C++11

详细

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

Test #1:

score: 5
Accepted
time: 189ms
memory: 1916kb

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: 199ms
memory: 1920kb

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: 172ms
memory: 1920kb

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: 177ms
memory: 1916kb

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: 168ms
memory: 1916kb

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: 186ms
memory: 1920kb

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: 193ms
memory: 1916kb

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: 201ms
memory: 1916kb

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: 176ms
memory: 1916kb

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: 163ms
memory: 1916kb

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: 164ms
memory: 1920kb

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: 183ms
memory: 1920kb

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: 165ms
memory: 1920kb

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: 183ms
memory: 1916kb

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: 170ms
memory: 1916kb

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: 194ms
memory: 1920kb

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: 193ms
memory: 1916kb

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: 169ms
memory: 1920kb

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: 173ms
memory: 1920kb

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: 162ms
memory: 1920kb

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

中文 English

Server time: 2025-03-16 03:41:53 | 开源项目