ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#185129 | #2680. Travel | snow_trace | 100 | 3580ms | 1920kb | C++11 | 1.0kb | 2023-09-23 08:36:37 | 2023-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;
}
详细
小提示:点击横条可展开更详细的信息
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