fork download
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<queue>
  5. #include<map>
  6. #include<cmath>
  7. #include<iomanip>
  8. #include<set>
  9. using namespace std;
  10. typedef long long ll;
  11. #define rep(i, n) for (int i = 0; i < n; ++i)
  12. #define rrep(i, st, n) for (int i = st; i < n; ++i)
  13. using pii = pair<int, int>;
  14.  
  15. int main() {
  16. const int inf = 300 * 100000;
  17. int n, m; cin >> n >> m;
  18. int dp[n + 1][n + 1]; rep(i, n + 1) rep(j, n + 1) dp[i][j] = inf;
  19. rep(i, m) {int u, v, l; cin >> u >> v >> l; dp[u][v] = l; dp[v][u] = l;}
  20. vector<int> v;
  21. v.resize(0);
  22. rrep(i, 1, n + 1) if (dp[i][1] != inf) v.push_back(i);
  23. int dp2[n + 1][n + 1]; rep(i, n + 1) rep(j, n + 1) dp2[i][j] = dp[i][j];
  24. rrep(i, 1, n + 1) {dp[1][i] = inf; dp[i][1] = inf;}
  25. //rrep(i, 1, n + 1) {rrep(j, 1, n + 1) cout << dp[i][j] << " "; cout << endl;}
  26. rrep(k, 1, n + 1) rrep(i, 1, n + 1) rrep(j, 1, n + 1) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
  27. //rrep(i, 1, n + 1) {rrep(j, 1, n + 1) cout << dp[i][j] << " "; cout << endl;}
  28. int ans = inf;
  29. rep(i, v.size()) rrep(j, i + 1, v.size()) ans = min(ans, dp2[1][v[i]] + dp[v[i]][v[j]] + dp2[v[j]][1]);
  30. if (ans != inf) cout << ans << endl;
  31. else cout << -1 << endl;
  32. }
  33.  
Success #stdin #stdout 0.02s 15816KB
stdin
300 300
1 2 100000
2 3 100000
3 4 100000
4 5 100000
5 6 100000
6 7 100000
7 8 100000
8 9 100000
9 10 100000
10 11 100000
11 12 100000
12 13 100000
13 14 100000
14 15 100000
15 16 100000
16 17 100000
17 18 100000
18 19 100000
19 20 100000
20 21 100000
21 22 100000
22 23 100000
23 24 100000
24 25 100000
25 26 100000
26 27 100000
27 28 100000
28 29 100000
29 30 100000
30 31 100000
31 32 100000
32 33 100000
33 34 100000
34 35 100000
35 36 100000
36 37 100000
37 38 100000
38 39 100000
39 40 100000
40 41 100000
41 42 100000
42 43 100000
43 44 100000
44 45 100000
45 46 100000
46 47 100000
47 48 100000
48 49 100000
49 50 100000
50 51 100000
51 52 100000
52 53 100000
53 54 100000
54 55 100000
55 56 100000
56 57 100000
57 58 100000
58 59 100000
59 60 100000
60 61 100000
61 62 100000
62 63 100000
63 64 100000
64 65 100000
65 66 100000
66 67 100000
67 68 100000
68 69 100000
69 70 100000
70 71 100000
71 72 100000
72 73 100000
73 74 100000
74 75 100000
75 76 100000
76 77 100000
77 78 100000
78 79 100000
79 80 100000
80 81 100000
81 82 100000
82 83 100000
83 84 100000
84 85 100000
85 86 100000
86 87 100000
87 88 100000
88 89 100000
89 90 100000
90 91 100000
91 92 100000
92 93 100000
93 94 100000
94 95 100000
95 96 100000
96 97 100000
97 98 100000
98 99 100000
99 100 100000
100 101 100000
101 102 100000
102 103 100000
103 104 100000
104 105 100000
105 106 100000
106 107 100000
107 108 100000
108 109 100000
109 110 100000
110 111 100000
111 112 100000
112 113 100000
113 114 100000
114 115 100000
115 116 100000
116 117 100000
117 118 100000
118 119 100000
119 120 100000
120 121 100000
121 122 100000
122 123 100000
123 124 100000
124 125 100000
125 126 100000
126 127 100000
127 128 100000
128 129 100000
129 130 100000
130 131 100000
131 132 100000
132 133 100000
133 134 100000
134 135 100000
135 136 100000
136 137 100000
137 138 100000
138 139 100000
139 140 100000
140 141 100000
141 142 100000
142 143 100000
143 144 100000
144 145 100000
145 146 100000
146 147 100000
147 148 100000
148 149 100000
149 150 100000
150 151 100000
151 152 100000
152 153 100000
153 154 100000
154 155 100000
155 156 100000
156 157 100000
157 158 100000
158 159 100000
159 160 100000
160 161 100000
161 162 100000
162 163 100000
163 164 100000
164 165 100000
165 166 100000
166 167 100000
167 168 100000
168 169 100000
169 170 100000
170 171 100000
171 172 100000
172 173 100000
173 174 100000
174 175 100000
175 176 100000
176 177 100000
177 178 100000
178 179 100000
179 180 100000
180 181 100000
181 182 100000
182 183 100000
183 184 100000
184 185 100000
185 186 100000
186 187 100000
187 188 100000
188 189 100000
189 190 100000
190 191 100000
191 192 100000
192 193 100000
193 194 100000
194 195 100000
195 196 100000
196 197 100000
197 198 100000
198 199 100000
199 200 100000
200 201 100000
201 202 100000
202 203 100000
203 204 100000
204 205 100000
205 206 100000
206 207 100000
207 208 100000
208 209 100000
209 210 100000
210 211 100000
211 212 100000
212 213 100000
213 214 100000
214 215 100000
215 216 100000
216 217 100000
217 218 100000
218 219 100000
219 220 100000
220 221 100000
221 222 100000
222 223 100000
223 224 100000
224 225 100000
225 226 100000
226 227 100000
227 228 100000
228 229 100000
229 230 100000
230 231 100000
231 232 100000
232 233 100000
233 234 100000
234 235 100000
235 236 100000
236 237 100000
237 238 100000
238 239 100000
239 240 100000
240 241 100000
241 242 100000
242 243 100000
243 244 100000
244 245 100000
245 246 100000
246 247 100000
247 248 100000
248 249 100000
249 250 100000
250 251 100000
251 252 100000
252 253 100000
253 254 100000
254 255 100000
255 256 100000
256 257 100000
257 258 100000
258 259 100000
259 260 100000
260 261 100000
261 262 100000
262 263 100000
263 264 100000
264 265 100000
265 266 100000
266 267 100000
267 268 100000
268 269 100000
269 270 100000
270 271 100000
271 272 100000
272 273 100000
273 274 100000
274 275 100000
275 276 100000
276 277 100000
277 278 100000
278 279 100000
279 280 100000
280 281 100000
281 282 100000
282 283 100000
283 284 100000
284 285 100000
285 286 100000
286 287 100000
287 288 100000
288 289 100000
289 290 100000
290 291 100000
291 292 100000
292 293 100000
293 294 100000
294 295 100000
295 296 100000
296 297 100000
297 298 100000
298 299 100000
299 300 100000
300 1 100000
stdout
-1