fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. int main() {
  7. 	int n, m, k; // Количество вершин, количество победителей и количество ребер
  8. 	cin >> n >> m >> k;
  9. 	vector<int> winner(m); // Вершины, которые нам нужно достичь
  10. 	for(int i = 0; i < m; i++) 
  11. 	{
  12. 		cin >> winner[i];
  13. 		winner[i]--; // В задаче отсчёт идёт с 1, поэтому мы уменьшаем все индексы на 1
  14. 	}
  15. 	vector<vector<vector<int>>> path(n); // Список смежности с весом
  16. 	for(int i = 0; i < k; i++)
  17. 	{
  18. 		int a, b, t;
  19. 		cin >> a >> b >> t; // Соединённые вершины и вес ребра
  20. 		a--;// Сдвиг индексов на 1
  21. 		b--;
  22. 		path[a].push_back({b, t}); // В список путей из вершины 'а' добавляем вершину 'b' и длину пути
  23. 		path[b].push_back({a, t}); 
  24. 	}
  25. 	int start; // Вершина, с которой мы начинаем
  26. 	cin >> start;
  27. 	start--; // Сдвигаем индекс
  28. 	vector<int> count(n, -1); // Счётчик длины путей
  29. 	count[start] = 0; // Мы находимся в этой вершине, поэтому дистанция до неё равна 0
  30. 	queue<int> plan; // Наш план посещения вершин. Так как мы используем BFS, то это контейнером является очередь
  31. 	plan.push(start); // Кладём нашу стартовую вершину в план
  32. 	while(!plan.empty()) // Наш BFS
  33. 	{
  34. 		start = plan.front(); 
  35. 		plan.pop();
  36. 		for(auto next: path[start]) // Достаём наши пары  вершина + вес
  37. 		{
  38. 			if(count[next[0]] == -1 || count[next[0]] > count[start] + next[1]) // Если вершина не посещена или путь через ту на котором мы сейчас более короткий
  39. 			{
  40. 				plan.push(next[0]); // Мы добавляем эту вершину в план
  41. 				count[next[0]] = count[start] + next[1]; // И отмечаем дистанцию до неё
  42. 			}
  43. 		}
  44. 	}
  45. 	bool delivered = true; // Предпологаем, что мы побывали во всех вершинах, которые нам нужны
  46. 	int longest = 0; // Положим максимальную дистанцию равной нулю
  47. 	for(int i = 0; i < m && delivered; i++)
  48. 	{
  49. 		if(count[winner[i]] == -1) // Если путь до нужной вершины не был найден
  50. 		{
  51. 			delivered = false; // Отмечаем, что мы побывали не везде, где надо
  52. 		}
  53. 		longest = max(count[winner[i]], longest);
  54. 	}
  55. 	if(delivered) // Если нужные вершины посещены
  56. 	{
  57. 		cout << "The good sponsor!\n" << longest; // Выводим фразу и длину пути до самой далёкой вершины
  58. 	}
  59. 	else
  60. 	{
  61. 		cout << "It is not fault of sponsor...";
  62. 	}
  63. 	return 0;
  64. }
Success #stdin #stdout 0s 4380KB
comments (?)
stdin
copy 
365 324 365
60 282 202 364 139 94 310 7 184 318 229 192 168 85 363 37 215 155 312 141 127 147 303 109 190 177 299 3 204 42 326 320 16 219 319 211 312 263 217 130 215 80 13 74 165 10 110 71 221 56 268 348 202 262 148 83 131 81 85 334 180 102 288 252 320 298 97 266 195 313 87 101 85 156 174 306 223 341 68 78 31 335 117 290 288 322 7 53 37 92 78 273 193 58 159 148 355 312 105 242 317 249 342 36 96 208 33 318 183 157 31 270 183 204 194 105 160 258 158 254 349 235 161 233 292 12 72 282 323 234 215 331 117 248 58 212 90 90 165 329 246 252 291 120 147 119 225 307 68 17 195 51 308 47 341 292 115 47 265 73 280 114 95 88 361 153 357 143 242 156 163 180 99 88 356 245 264 215 186 331 288 72 74 288 119 49 214 290 152 113 362 124 226 149 211 278 301 202 112 234 49 275 105 204 54 96 84 317 310 326 340 290 90 48 212 265 153 60 189 361 172 243 119 89 26 330 58 326 223 170 251 329 79 356 167 132 86 250 141 87 268 115 68 357 219 279 256 63 30 136 58 258 13 177 346 38 198 96 55 112 265 306 75 35 353 242 223 130 183 363 273 85 169 341 133 79 254 80 141 284 216 199 233 228 10 214 323 264 309 69 10 265 66 85 299 53 18 156 182 200 211 90 342 71 122 109 150 10 246 290 350 96 123 218 15 189 123 29 144 123 155 154 22 220 295 12 273
312 224 146
146 69 292
179 140 48
345 346 115
225 270 99
12 85 8
83 330 187
169 109 309
323 262 22
177 191 90
141 194 314
287 31 74
270 210 270
318 189 250
67 105 212
222 116 296
287 255 260
108 58 3
109 15 321
187 249 203
277 24 31
282 2 62
47 272 328
9 224 151
258 347 312
161 203 62
148 181 8
100 346 66
159 89 137
115 332 20
317 300 44
40 216 45
158 320 8
120 328 231
327 277 212
273 73 107
26 220 344
33 319 324
98 113 47
292 284 71
311 292 5
46 331 221
148 180 232
155 299 194
78 260 105
346 224 177
144 249 89
123 282 42
81 71 211
185 54 186
255 57 113
259 102 135
171 306 315
37 153 305
287 287 200
27 267 115
260 46 364
348 225 337
82 362 99
292 181 153
113 127 209
282 21 2
51 248 308
365 342 152
362 263 73
196 289 31
2 184 133
365 166 357
28 304 354
127 231 226
279 35 353
179 316 65
180 58 4
179 115 345
22 111 243
94 363 223
125 364 98
257 56 321
306 83 259
294 209 181
211 179 215
255 357 222
319 229 337
323 42 86
359 64 196
293 214 250
151 338 248
248 287 303
260 227 21
154 212 286
334 114 100
241 4 148
154 322 11
125 336 110
210 330 230
97 314 135
346 99 165
229 39 86
223 298 4
300 86 272
221 112 20
12 352 23
216 140 37
284 322 64
28 166 85
314 263 34
83 300 132
304 220 227
81 78 160
84 12 302
47 289 48
67 357 91
146 208 288
182 126 244
246 210 101
330 215 55
363 354 355
187 293 209
48 8 343
264 149 355
258 195 335
305 261 327
88 42 226
67 280 351
310 160 195
102 182 44
157 236 32
146 57 16
46 162 24
24 117 172
70 9 1
39 6 319
57 93 360
282 216 331
324 160 126
153 261 364
253 109 234
342 254 291
357 300 144
15 15 260
243 84 269
301 179 331
254 236 115
305 209 330
270 168 181
87 12 133
85 265 242
319 298 130
301 289 121
136 361 135
30 295 275
355 230 89
320 118 16
126 114 224
90 19 83
270 105 95
38 247 51
279 200 40
100 192 328
278 327 15
104 356 310
14 38 231
102 49 349
174 175 97
32 264 172
172 226 334
266 263 215
8 233 49
47 24 297
66 301 258
81 40 305
82 110 342
312 268 83
352 76 257
141 164 212
312 335 72
280 292 26
186 356 315
291 37 339
222 160 274
114 240 5
54 13 171
87 16 130
169 60 205
117 200 61
329 203 87
92 175 14
118 360 61
124 286 98
97 142 257
63 256 188
124 1 257
295 87 329
59 313 23
321 64 222
73 84 60
159 176 234
229 350 285
290 108 205
79 262 347
27 324 294
271 82 294
162 68 72
182 184 19
205 196 83
61 268 166
177 61 33
102 290 74
22 271 182
283 349 78
264 67 93
192 337 174
177 190 299
249 6 117
324 210 4
41 328 271
264 196 331
353 355 312
62 68 274
300 350 314
12 306 15
104 189 43
334 1 232
324 306 238
132 264 139
135 362 158
40 317 354
63 304 35
66 57 102
340 356 143
288 59 83
303 219 272
345 188 329
269 203 269
198 335 224
28 104 220
186 144 171
231 263 167
265 328 223
58 302 271
200 225 329
340 219 183
246 255 62
266 158 264
169 47 233
27 75 337
304 260 172
166 182 69
332 81 31
247 195 333
152 86 249
172 60 159
354 362 48
50 262 263
6 122 309
238 206 75
266 144 26
72 309 207
197 333 344
285 271 173
309 114 259
192 285 318
350 331 315
89 72 268
43 77 25
44 315 230
118 215 8
144 344 8
42 232 32
21 151 302
250 94 107
143 342 27
153 18 357
159 164 63
61 206 140
85 249 146
314 59 52
13 259 87
21 300 319
109 12 161
46 262 255
209 39 288
235 248 306
283 41 104
38 102 1
234 243 307
71 192 365
122 261 315
266 338 306
219 82 318
14 184 214
325 27 309
305 319 192
245 293 232
40 330 25
97 255 268
38 325 151
94 139 46
43 39 19
349 314 157
358 327 340
206 344 58
149 283 11
32 219 304
321 315 325
37 46 215
361 84 231
146 177 4
249 277 42
324 317 355
115 309 9
146 206 44
203 46 18
271 78 236
209 90 185
168 126 287
74 122 5
305 324 239
308 207 207
42 222 215
88 28 215
153 230 55
196 68 157
213 338 291
140 238 15
16 40 198
303 114 319
307 110 277
237 52 176
78 150 89
349 238 117
198 25 38
252 278 105
101 182 134
26 322 63
41 337 103
238 274 273
248 273 17
216 201 125
26 336 332
172 319 204
345 152 285
17 95 254
179 195 71
4 221 27
67 318 55
169 190 329
133 129 293
206 344 185
22 62 155
353 233 109
248 212 260
225 285 354
113 98 184
183 102 96
266 168 48
321 28 294
341 217 57
268 57 35
87 135 96
299 180 20
42 62 288
358 286 208
38 91 362
278
stdout
copy 
It is not fault of sponsor...
https://ideone.com/PCeoEV
Задача для публикации(3) Через список смежности
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!