ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185133 | #2680. Travel | wosile | 100 | 2710ms | 2280kb | C++ | 1.0kb | 2023-09-23 08:59:09 | 2023-09-23 12:10:06 |
answer
#include<bits/stdc++.h>
#define inf make_pair(0x3f3f3f3f,0x3f3f3f3f)
using namespace std;
int n,m,L;
pair<int,int>dis[305][305];
int vis[305];
int w[305][305];
int main(){
scanf("%d%d%d",&n,&m,&L);
memset(w,0x3f,sizeof(w));
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=inf;
for(int i=1;i<=m;i++){
int u,v,W;
scanf("%d%d%d",&u,&v,&W);
w[u][v]=min(w[u][v],W);
w[v][u]=min(w[v][u],W);
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
dis[i][i]=make_pair(0,0);
int cnt=0;
while(cnt<n){
cnt++;
pair<int,int>p=inf;
int x=0;
for(int j=1;j<=n;j++)if(dis[i][j]<p && vis[j]==0)p=dis[i][j],x=j;
vis[x]=1;
for(int j=1;j<=n;j++)if(w[x][j]<=L){
pair<int,int>d=dis[i][x];
if(w[x][j]+dis[i][x].second<=L)d.second+=w[x][j];
else{
d.first++;
d.second=w[x][j];
}
if(d<dis[i][j])dis[i][j]=d;
}
}
}
int Q;
scanf("%d",&Q);
while(Q--){
int s,t;
scanf("%d%d",&s,&t);
if(dis[s][t]<inf)printf("%d\n",dis[s][t].first);
else printf("-1\n");
}
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 139ms
memory: 2272kb
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: 141ms
memory: 2280kb
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: 144ms
memory: 2276kb
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: 130ms
memory: 2272kb
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: 130ms
memory: 2272kb
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: 110ms
memory: 2276kb
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: 127ms
memory: 2276kb
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: 134ms
memory: 2272kb
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: 135ms
memory: 2272kb
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: 140ms
memory: 2276kb
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: 145ms
memory: 2272kb
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: 130ms
memory: 2272kb
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: 148ms
memory: 2276kb
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: 137ms
memory: 2276kb
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: 128ms
memory: 2276kb
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: 136ms
memory: 2276kb
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: 143ms
memory: 2276kb
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: 160ms
memory: 2276kb
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: 125ms
memory: 2276kb
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: 128ms
memory: 2280kb
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