UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214148#2680. Travelsdy03196ms1948kbC++813b2024-11-15 20:17:412024-11-15 23:25:19

answer

#include <bits/stdc++.h>
using namespace std;

const int maxn = 310,  inf = 0x3f3f3f3f;

int n, m, l;
int g[maxn][maxn], f[maxn][maxn];

void floyd(int d[maxn][maxn]) {
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main() {
	cin >> n >> m >> l;
	memset(g, 0x3f, sizeof(g));
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u][v] = g[v][u] = w;
	}
	floyd(g);
	memset(f, 0x3f, sizeof(f));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (g[i][j] <= l)
				f[i][j] = 1;
	floyd(f);
	int q;
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		cin >> u >> v;
		cout << (f[u][v] == inf ? -1 : f[u][v] - 1) << endl;
	}
	return 0;
}

Details

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

Test #1:

score: 0
Wrong Answer
time: 158ms
memory: 1948kb

input:

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

output:

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

result:

wrong answer 2nd lines differ - expected: '3', found: '2'

Test #2:

score: 0
Wrong Answer
time: 143ms
memory: 1944kb

input:

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

output:

3
3
4
5
5
4
4
4
-1
-1
2
2
1
3
2
2
3
3
3
3
4
4
3
1
3
4
2
3
3
4
3
4
4
3
4
3
2
4
3
2
4
2
2
3
6
4
3
-1
3...

result:

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

Test #3:

score: 0
Wrong Answer
time: 150ms
memory: 1944kb

input:

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

output:

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

result:

wrong answer 2nd lines differ - expected: '3', found: '2'

Test #4:

score: 0
Wrong Answer
time: 160ms
memory: 1944kb

input:

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

output:

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

result:

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

Test #5:

score: 0
Wrong Answer
time: 161ms
memory: 1948kb

input:

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

output:

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

result:

wrong answer 2nd lines differ - expected: '1', found: '2'

Test #6:

score: 0
Wrong Answer
time: 165ms
memory: 1944kb

input:

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

output:

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

result:

wrong answer 3rd lines differ - expected: '-1', found: '10'

Test #7:

score: 0
Wrong Answer
time: 166ms
memory: 1944kb

input:

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

output:

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

result:

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

Test #8:

score: 0
Wrong Answer
time: 160ms
memory: 1948kb

input:

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

output:

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

result:

wrong answer 4th lines differ - expected: '2', found: '1'

Test #9:

score: 0
Wrong Answer
time: 200ms
memory: 1944kb

input:

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

output:

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

result:

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

Test #10:

score: 0
Wrong Answer
time: 166ms
memory: 1944kb

input:

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

output:

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

result:

wrong answer 2nd lines differ - expected: '1', found: '2'

Test #11:

score: 0
Wrong Answer
time: 171ms
memory: 1944kb

input:

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

output:

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

result:

wrong answer 2nd lines differ - expected: '1', found: '0'

Test #12:

score: 0
Wrong Answer
time: 176ms
memory: 1944kb

input:

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

output:

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

result:

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

Test #13:

score: 0
Wrong Answer
time: 145ms
memory: 1944kb

input:

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

output:

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

result:

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

Test #14:

score: 0
Wrong Answer
time: 169ms
memory: 1948kb

input:

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

output:

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

result:

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

Test #15:

score: 0
Wrong Answer
time: 151ms
memory: 1944kb

input:

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

output:

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

result:

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

Test #16:

score: 0
Wrong Answer
time: 143ms
memory: 1944kb

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

result:

wrong answer 8th lines differ - expected: '1', found: '0'

Test #17:

score: 0
Wrong Answer
time: 178ms
memory: 1948kb

input:

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

output:

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

result:

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

Test #18:

score: 0
Wrong Answer
time: 121ms
memory: 1948kb

input:

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

output:

4
5
-1
5
5
6
3
5
4
4
4
2
5
5
5
5
5
6
5
5
1
3
4
4
2
5
3
4
3
6
5
-1
4
3
3
-1
4
4
3
4
5
-1
4
6
-1
2
7
1...

result:

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

Test #19:

score: 0
Wrong Answer
time: 157ms
memory: 1944kb

input:

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

output:

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

result:

wrong answer 3rd lines differ - expected: '0', found: '2'

Test #20:

score: 0
Wrong Answer
time: 156ms
memory: 1948kb

input:

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

output:

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

result:

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