fork download
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6. typedef pair<int,int> ii;
  7. typedef vector<ii> vii;
  8. #define MAXN 1001
  9. #define LIMIT 1000001
  10. #define MP make_pair
  11. vii grafo[MAXN];
  12. int matriz[MAXN][MAXN],tempo[MAXN],resposta=LIMIT,visitado[MAXN][MAXN];
  13. int main(){
  14. int n,m;
  15. scanf("%d %d",&n,&m);
  16. for(int i=1;i<=n;i++){
  17. scanf("%d",&tempo[i]);
  18. for(int j=1;j<=n;j++) matriz[i][j] = LIMIT;
  19. }
  20. for(int i=1;i<=m;i++){
  21. int u,v,duracao;
  22. scanf("%d %d %d",&u,&v,&duracao);
  23. grafo[u].push_back(MP(tempo[v]+duracao,v));
  24. }
  25. for(int i=1;i<=n;i++) {
  26. priority_queue<ii, vii, greater<ii> > heap;
  27. for(int j=0;j<(int)grafo[i].size();j++) heap.push(grafo[i][j]);
  28. while(!heap.empty()){
  29. ii davez = heap.top();
  30. heap.pop();
  31. if (visitado[i][davez.second]) continue;
  32. visitado[i][davez.second] = 1;
  33. matriz[i][davez.second] = davez.first;
  34. for(int j=0;j<(int)grafo[davez.second].size();j++) heap.push(MP(davez.first+grafo[davez.second][j].first,grafo[davez.second][j].second));
  35. }
  36. }
  37. for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) resposta = min(resposta,matriz[i][j]+matriz[j][i]);
  38. printf("%d\n",resposta);
  39. return 0;
  40. }
Success #stdin #stdout 0.02s 11312KB
stdin
302 564
936 1200 192 1339 16 751 147 518 732 1268 195 1204 74 159 659 1248 1464 80 1589 464 400 542 985 769 1367 1215 1542 815 1318 361 87 1474 1381 23 968 603 1315 535 1404 1310 765 1520 349 811 301 1366 1324 860 746 690 1302 762 1316 1205 426 227 296 1491 1227 1177 650 1113 1478 419 497 1389 59 1534 869 1297 427 1421 349 1492 753 199 391 1393 1541 1419 1120 962 421 901 698 327 1481 660 1312 588 1516 794 1264 307 1530 141 1406 1187 877 1438 783 1076 491 619 1072 600 189 734 1411 1584 1134 303 168 885 956 1513 1049 387 370 601 744 815 1518 1129 1442 1096 13 1455 821 918 1551 592 332 855 1020 866 984 446 1204 757 305 1094 1163 1414 1435 1261 1344 226 513 987 395 502 47 385 901 1465 1257 909 919 216 130 1310 92 1087 484 1144 601 142 507 1415 1470 684 694 464 992 624 1038 1382 1025 808 425 309 318 1372 546 291 691 916 1240 433 1129 936 83 607 506 856 1287 1212 890 1088 78 832 1154 729 811 972 1438 1156 831 1143 1393 421 1313 960 1157 702 1124 851 44 74 913 1174 1184 1030 514 1297 1153 901 391 689 22 99 815 441 1140 815 1423 2 1326 1421 1004 1045 1350 528 866 1568 329 574 448 753 607 797 862 663 1483 582 570 893 977 943 1379 1272 1344 1409 1100 469 904 800 142 482 1262 717 1328 1341 1139 28 225 1405 1436 1124 500 1456 384 1577 1293 820 1 1007 225 327 1229 759 398 758 897 562 1373 1280 189 173 241 1561
96 82 105
36 30 903
206 174 785
247 205 1263
202 196 745
71 81 88
114 109 11
128 178 529
88 238 1278
170 186 1216
228 132 1215
54 68 772
111 236 971
140 135 1587
186 194 709
214 175 528
58 179 1596
132 60 409
198 116 1217
169 134 994
101 53 1046
133 190 1189
118 224 1362
199 51 630
147 139 1046
154 209 954
139 63 386
222 235 163
188 175 1413
255 59 1455
91 234 298
56 104 32
202 210 1032
179 219 155
177 242 1444
96 187 807
54 66 168
235 96 1486
230 211 1392
187 64 814
176 209 1006
221 73 768
222 179 49
60 83 887
43 60 280
156 242 987
116 153 646
96 150 514
100 110 593
211 180 957
138 95 931
77 222 1213
109 76 1543
182 159 805
107 106 1
24 86 584
182 243 338
103 63 1199
201 104 1128
59 47 300
122 158 487
144 133 1027
193 77 375
241 249 842
224 121 427
127 205 1521
223 131 334
240 152 424
70 78 243
207 87 662
37 84 1521
149 202 116
83 50 623
123 240 1263
90 117 41
236 189 1314
141 111 1009
57 43 183
121 118 980
136 78 319
200 111 1370
195 159 1402
124 217 1141
58 97 886
140 88 242
238 217 357
216 165 146
48 130 670
209 129 482
73 130 1541
85 42 1062
178 232 747
55 199 382
245 246 1366
174 110 1021
98 156 671
32 70 1221
152 244 1229
62 51 621
183 221 787
58 62 79
97 246 722
65 224 275
190 228 881
162 253 1592
39 67 1570
92 245 1060
197 244 31
74 90 1191
254 183 305
43 216 1277
72 38 1028
225 169 1193
29 44 1126
205 261 1002
41 25 987
170 176 1412
34 52 1472
143 229 485
201 257 848
251 229 395
210 234 61
51 75 1213
179 229 1265
50 194 65
199 239 401
192 82 707
67 58 86
231 220 1353
153 60 1139
177 99 1495
187 178 921
144 108 443
157 237 754
105 71 1379
252 208 54
195 211 88
93 168 1279
57 212 419
117 79 98
231 124 1012
97 154 1003
94 64 1076
190 99 1169
235 252 693
68 158 1334
42 96 1454
51 35 741
241 88 1211
126 174 660
151 202 239
112 50 601
61 76 948
241 92 557
148 126 785
52 101 1050
164 73 1333
31 42 703
124 254 347
219 127 72
85 56 1161
103 214 1164
214 129 1177
95 195 1043
178 165 1132
161 156 1052
143 225 1114
252 203 841
246 225 1371
204 228 1596
106 192 760
76 164 929
187 102 1323
238 230 1205
162 193 973
48 33 671
120 187 559
64 86 1547
237 218 538
66 142 1254
98 114 83
210 233 1424
40 28 1562
198 231 1545
76 49 121
136 172 1573
240 125 516
42 162 1192
101 148 1155
226 215 204
100 170 1174
202 59 290
189 241 1410
247 52 733
238 93 749
186 144 418
45 242 1064
69 57 1317
181 139 788
150 210 194
90 92 922
68 98 276
249 84 264
74 223 520
206 235 895
93 24 225
50 48 433
92 101 697
183 56 301
216 237 1410
245 105 948
73 72 899
82 92 539
227 80 664
174 79 1252
196 187 833
194 212 1427
56 27 95
175 238 1448
56 173 738
236 232 539
243 85 1599
191 198 1137
134 62 883
69 168 989
98 66 946
126 77 1053
102 91 778
197 215 1134
223 198 1289
246 249 385
209 207 1513
82 39 643
181 176 1200
125 149 1169
179 175 783
72 120 1288
27 79 708
97 85 1283
175 113 507
261 90 1059
155 113 339
182 119 692
153 112 748
28 45 1601
159 210 37
79 188 437
86 100 774
201 191 1285
53 40 981
108 252 1392
59 69 403
205 97 563
180 48 1027
95 167 1380
52 146 278
212 216 104
68 61 641
75 136 1314
151 206 155
184 53 1045
160 45 647
184 105 707
64 54 8
217 44 1295
26 93 953
161 192 599
213 192 98
46 31 822
165 203 308
110 209 1517
55 146 1573
67 89 32
208 201 1131
93 108 1037
228 241 457
185 132 189
85 121 1305
210 171 590
145 204 90
86 77 1361
122 81 575
112 55 1398
234 200 362
156 195 1105
215 116 499
119 166 245
75 58 749
81 115 941
63 101 415
254 161 1195
217 137 1077
94 134 706
169 184 387
142 140 1444
74 180 1161
147 65 637
259 248 585
128 71 357
87 26 945
242 186 901
82 125 1334
44 144 727
115 238 1204
260 256 1102
159 188 34
225 222 1040
111 194 728
91 29 368
142 193 8
79 107 1273
203 226 1557
141 230 53
101 151 749
55 41 358
89 71 146
138 197 723
117 219 1355
59 131 193
230 135 1544
164 107 425
229 95 776
178 200 1289
221 90 44
148 201 1176
240 254 546
244 189 1310
152 232 1126
213 220 257
145 258 978
155 154 1375
71 207 571
248 217 538
160 166 1468
99 259 214
89 173 1078
99 83 129
163 181 1326
228 255 326
232 224 180
172 119 523
222 96 91
185 197 1002
214 138 699
250 203 993
165 127 1526
233 155 68
88 74 240
209 260 1319
234 167 442
87 58 329
125 236 1563
189 171 579
204 214 123
250 208 964
71 72 133
25 34 1025
127 164 370
226 230 424
81 177 155
204 160 657
84 98 1061
99 46 319
230 234 1115
224 128 1468
211 61 755
106 85 895
180 227 693
183 220 776
76 87 671
131 172 1293
123 109 420
70 157 49
121 191 1028
139 204 1050
60 222 936
167 57 175
208 70 410
185 72 1211
62 190 1190
137 185 1046
243 176 1144
232 54 1229
186 143 188
102 114 1148
232 233 762
258 74 358
194 179 1448
168 231 1455
176 183 203
119 74 591
177 84 1466
219 196 404
81 55 453
173 240 156
171 227 451
213 98 1324
64 120 1099
239 228 577
193 240 434
62 122 956
225 106 153
135 211 664
44 59 278
256 46 445
237 204 909
196 212 539
149 122 503
207 251 27
38 87 1497
49 75 1021
115 93 142
197 141 986
46 191 440
80 136 283
53 137 352
131 161 261
146 49 12
133 68 1142
114 219 701
95 73 344
78 145 1324
244 218 249
207 170 987
229 243 1108
229 245 677
130 163 1183
195 57 537
78 36 1057
253 213 711
218 248 324
134 86 610
66 126 1483
60 66 796
92 61 1444
192 140 979
130 103 717
158 83 1477
88 199 380
105 94 741
196 198 453
69 141 8
61 55 1289
118 128 430
242 188 998
77 99 532
248 169 1164
79 102 574
65 81 1363
33 88 963
89 201 1005
239 118 807
200 251 951
129 213 856
173 205 561
84 97 1121
243 67 719
208 221 564
175 178 1481
83 182 478
100 32 646
220 177 446
205 250 382
63 95 62
188 206 1208
65 150 325
70 115 1320
110 62 1536
146 102 984
215 94 1129
231 193 1249
45 64 1144
194 100 947
120 117 1469
78 207 810
104 82 1172
198 91 1124
107 138 450
137 231 234
135 184 73
220 195 1238
221 236 99
129 183 1255
102 163 838
224 237 1478
84 147 622
236 196 911
168 181 1312
216 247 1489
257 225 522
189 186 1100
249 223 1440
63 243 494
80 241 859
66 100 1419
212 56 1561
181 226 1087
215 182 381
199 78 1377
190 202 868
150 250 597
192 216 830
217 215 966
227 208 415
61 157 1061
200 190 1265
191 218 833
57 226 1172
108 155 663
237 69 67
86 223 449
218 214 510
73 47 1518
154 152 577
226 177 269
77 68 90
83 235 1186
166 67 367
184 181 76
211 69 1055
233 123 1466
113 43 384
242 133 1072
132 112 962
234 239 1033
80 65 1588
94 37 555
116 185 943
113 147 446
227 253 1431
163 103 1132
239 148 255
87 142 1315
104 80 17
218 70 750
91 180 189
157 65 1237
72 206 1251
176 200 123
206 123 869
191 153 96
47 89 638
233 221 266
172 143 945
167 145 401
30 63 614
219 233 49
203 199 1278
35 80 900
188 247 682
193 75 154
220 189 33
67 94 644
75 239 499
203 162 888
235 182 1137
223 185 997
251 91 517
180 151 1110
90 149 1094
166 197 13
49 124 10
212 184 1199
158 160 616
stdout
4183