ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214148 | #2680. Travel | sdy | 0 | 3196ms | 1948kb | C++ | 813b | 2024-11-15 20:17:41 | 2024-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'