#include <bits/stdc++.h>
using namespace std;
#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= b; --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)
#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second
#define BIG 1000000000000000000
typedef long long ll;
typedef long double ld;
void cpr(string s, vector<int> v)
{ int i = 0; for (char c : s) { if (c == '$') cout << v[i++]; else cout << c; } cout << '\n'; }
void cpr(string s) { cpr(s, {}); }
void solve();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
const int borne = 101*1000;
int nbNod, nbLi;
int depri, arpri, dean, aran;
vector<pair<int,int>> adj[borne];
vector<int> pcc[borne];
int orig = 0;
vector<int> green[2][borne];
void rundij(int dep)
{
vector<int> md(nbNod, -1);
md[dep] = 0;
priority_queue<pair<int, int>> dij;
dij.push({0, dep});
while (!dij.empty()) {
int dist = -dij.top().fi, nod = dij.top().se;
dij.pop();
if (dist != md[nod]) continue;
for (auto lien : adj[nod]) {
int vo = lien.fi, poids = lien.se;
int nd = dist+poids;
if (md[vo] == -1 || nd < md[vo]) {
md[vo] = nd;
dij.push({-nd, vo});
}
}
}
form(i, nbNod) assert(md[i] != -1);
pcc[dep] = md;
}
pair<int, int> nodtri[borne];
void comp()
{
for (int nod = 0; nod < nbNod; ++nod) {
nodtri[nod] = {pcc[dean][nod], nod};
for (auto lien : adj[nod]) {
int vo = lien.fi, poids = lien.se;
int neworig = pcc[depri][nod] + poids + pcc[arpri][vo];
int neworig2 = pcc[arpri][nod] + poids + pcc[depri][vo];
if (neworig == orig) {
green[0][nod].push_back(vo);
}
if (neworig2 == orig) {
green[1][nod].push_back(vo);
}
}
}
sort(nodtri, nodtri+nbNod);
}
int tot = LLONG_MAX;
int mode = 0;
bool vu[2][borne];
int mku = 0;
void dfs(int nod)
{
vu[mode][nod] = true;
chmin(tot, mku + pcc[aran][nod]);
for (int vo : green[mode][nod]) {
if (! vu[mode][vo]) {
dfs(vo);
}
}
}
void solve()
{
cin >> nbNod >> nbLi;
cin >> depri >> arpri;
cin >> dean >> aran;
--depri; --arpri; --dean; --aran;
for (int ind = 0; ind < nbLi; ++ind) {
int x, y, p;
cin >> x >> y >> p;
--x; --y;
adj[x].push_back({y,p});
adj[y].push_back({x,p});
}
rundij(depri);
rundij(arpri);
rundij(dean);
rundij(aran);
orig = pcc[depri][arpri];
comp();
for (; mode < 2; ++mode) {
for (int i = 0; i < nbNod; ++i) {
mku = nodtri[i].fi;
int dep = nodtri[i].se;
if (vu[mode][dep]) continue;
dfs(dep);
}
}
cout << tot << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
388 ms |
31376 KB |
Output is correct |
2 |
Correct |
437 ms |
29820 KB |
Output is correct |
3 |
Correct |
518 ms |
33756 KB |
Output is correct |
4 |
Correct |
444 ms |
29436 KB |
Output is correct |
5 |
Correct |
396 ms |
30392 KB |
Output is correct |
6 |
Correct |
462 ms |
31484 KB |
Output is correct |
7 |
Correct |
449 ms |
30968 KB |
Output is correct |
8 |
Correct |
399 ms |
30772 KB |
Output is correct |
9 |
Correct |
348 ms |
30528 KB |
Output is correct |
10 |
Correct |
371 ms |
30492 KB |
Output is correct |
11 |
Correct |
197 ms |
24804 KB |
Output is correct |
12 |
Correct |
429 ms |
30480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
445 ms |
31452 KB |
Output is correct |
2 |
Correct |
422 ms |
31196 KB |
Output is correct |
3 |
Correct |
395 ms |
31328 KB |
Output is correct |
4 |
Correct |
416 ms |
31148 KB |
Output is correct |
5 |
Correct |
407 ms |
31240 KB |
Output is correct |
6 |
Correct |
452 ms |
33920 KB |
Output is correct |
7 |
Correct |
449 ms |
34184 KB |
Output is correct |
8 |
Correct |
470 ms |
31344 KB |
Output is correct |
9 |
Correct |
486 ms |
31456 KB |
Output is correct |
10 |
Correct |
437 ms |
31064 KB |
Output is correct |
11 |
Correct |
198 ms |
27624 KB |
Output is correct |
12 |
Correct |
442 ms |
34216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
11640 KB |
Output is correct |
2 |
Correct |
10 ms |
9948 KB |
Output is correct |
3 |
Correct |
9 ms |
9848 KB |
Output is correct |
4 |
Correct |
29 ms |
13248 KB |
Output is correct |
5 |
Correct |
18 ms |
11512 KB |
Output is correct |
6 |
Correct |
9 ms |
9976 KB |
Output is correct |
7 |
Correct |
10 ms |
9976 KB |
Output is correct |
8 |
Correct |
11 ms |
10104 KB |
Output is correct |
9 |
Correct |
13 ms |
9976 KB |
Output is correct |
10 |
Correct |
22 ms |
11512 KB |
Output is correct |
11 |
Correct |
9 ms |
9820 KB |
Output is correct |
12 |
Correct |
9 ms |
9848 KB |
Output is correct |
13 |
Correct |
9 ms |
9852 KB |
Output is correct |
14 |
Correct |
12 ms |
9848 KB |
Output is correct |
15 |
Correct |
9 ms |
9976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
388 ms |
31376 KB |
Output is correct |
2 |
Correct |
437 ms |
29820 KB |
Output is correct |
3 |
Correct |
518 ms |
33756 KB |
Output is correct |
4 |
Correct |
444 ms |
29436 KB |
Output is correct |
5 |
Correct |
396 ms |
30392 KB |
Output is correct |
6 |
Correct |
462 ms |
31484 KB |
Output is correct |
7 |
Correct |
449 ms |
30968 KB |
Output is correct |
8 |
Correct |
399 ms |
30772 KB |
Output is correct |
9 |
Correct |
348 ms |
30528 KB |
Output is correct |
10 |
Correct |
371 ms |
30492 KB |
Output is correct |
11 |
Correct |
197 ms |
24804 KB |
Output is correct |
12 |
Correct |
429 ms |
30480 KB |
Output is correct |
13 |
Correct |
445 ms |
31452 KB |
Output is correct |
14 |
Correct |
422 ms |
31196 KB |
Output is correct |
15 |
Correct |
395 ms |
31328 KB |
Output is correct |
16 |
Correct |
416 ms |
31148 KB |
Output is correct |
17 |
Correct |
407 ms |
31240 KB |
Output is correct |
18 |
Correct |
452 ms |
33920 KB |
Output is correct |
19 |
Correct |
449 ms |
34184 KB |
Output is correct |
20 |
Correct |
470 ms |
31344 KB |
Output is correct |
21 |
Correct |
486 ms |
31456 KB |
Output is correct |
22 |
Correct |
437 ms |
31064 KB |
Output is correct |
23 |
Correct |
198 ms |
27624 KB |
Output is correct |
24 |
Correct |
442 ms |
34216 KB |
Output is correct |
25 |
Correct |
18 ms |
11640 KB |
Output is correct |
26 |
Correct |
10 ms |
9948 KB |
Output is correct |
27 |
Correct |
9 ms |
9848 KB |
Output is correct |
28 |
Correct |
29 ms |
13248 KB |
Output is correct |
29 |
Correct |
18 ms |
11512 KB |
Output is correct |
30 |
Correct |
9 ms |
9976 KB |
Output is correct |
31 |
Correct |
10 ms |
9976 KB |
Output is correct |
32 |
Correct |
11 ms |
10104 KB |
Output is correct |
33 |
Correct |
13 ms |
9976 KB |
Output is correct |
34 |
Correct |
22 ms |
11512 KB |
Output is correct |
35 |
Correct |
9 ms |
9820 KB |
Output is correct |
36 |
Correct |
9 ms |
9848 KB |
Output is correct |
37 |
Correct |
9 ms |
9852 KB |
Output is correct |
38 |
Correct |
12 ms |
9848 KB |
Output is correct |
39 |
Correct |
9 ms |
9976 KB |
Output is correct |
40 |
Correct |
377 ms |
32164 KB |
Output is correct |
41 |
Correct |
351 ms |
31264 KB |
Output is correct |
42 |
Correct |
345 ms |
31276 KB |
Output is correct |
43 |
Correct |
183 ms |
29684 KB |
Output is correct |
44 |
Correct |
207 ms |
29592 KB |
Output is correct |
45 |
Correct |
379 ms |
35172 KB |
Output is correct |
46 |
Correct |
462 ms |
34876 KB |
Output is correct |
47 |
Correct |
472 ms |
32164 KB |
Output is correct |
48 |
Correct |
261 ms |
28004 KB |
Output is correct |
49 |
Correct |
348 ms |
31680 KB |
Output is correct |
50 |
Correct |
428 ms |
33620 KB |
Output is correct |
51 |
Correct |
407 ms |
35284 KB |
Output is correct |