UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185133#2680. Travelwosile1002710ms2280kbC++1.0kb2023-09-23 08:59:092023-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;
}

详细

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

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