///
/// ♪ Pizza mozzarella rella rella rella... ♪
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
typedef long long ll;
typedef std::pair<ll,ll> pll;
using namespace std;
const int N = 100'010;
const ll inf = 1e15;
int n, m;
int s, t;
int u, v;
vector<ll> dij(vector<pll>* A, int s, int n, vector<int>* par = NULL)
{
vector<ll> dis(n);
set<pll> pq;
Loop(i,0,n) dis[i] = (i==s?0:inf);
pq.emplace(0,s);
while(pq.size())
{
auto v = pq.begin()->second;
pq.erase(pq.begin());
for(auto [u, w] : A[v])
{
if(dis[v] + w < dis[u])
{
if(par) par[u].clear();
pq.erase ({dis[u], u});
dis[u] = dis[v] + w;
pq.insert({dis[u], u});
}
if(dis[v] + w == dis[u] && par)
par[u].push_back(v);
}
}
return dis;
}
vector<pll> A[4*N];
vector<int> par[N];
bool vis[N];
void jotaro(int v)
{
vis[v] = 1;
for(auto p : par[v]){
A[n+p].emplace_back(n+v,0);
A[2*n+v].emplace_back(2*n+p,0);
if(!vis[p])
jotaro(p);
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m >> s >> t >> u >> v;
--s; --t; --u; --v;
Loop(_,0,m)
{
int v, u, w;
cin >> v >> u >> w;
--v; --u;
A[v].emplace_back(u,w);
A[u].emplace_back(v,w);
A[3*n+v].emplace_back(3*n+u,w);
A[3*n+u].emplace_back(3*n+v,w);
}
dij(A, s, n, par);
jotaro(t);
Loop(i,0,n)
{
A[0*n+i].emplace_back(1*n+i, 0);
A[0*n+i].emplace_back(2*n+i, 0);
A[1*n+i].emplace_back(3*n+i, 0);
A[2*n+i].emplace_back(3*n+i, 0);
}
cout << dij(A, v, 4*n)[3*n+u] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
806 ms |
59232 KB |
Output is correct |
2 |
Correct |
773 ms |
57980 KB |
Output is correct |
3 |
Correct |
815 ms |
68608 KB |
Output is correct |
4 |
Correct |
757 ms |
59208 KB |
Output is correct |
5 |
Correct |
762 ms |
59984 KB |
Output is correct |
6 |
Correct |
775 ms |
59440 KB |
Output is correct |
7 |
Correct |
747 ms |
59716 KB |
Output is correct |
8 |
Correct |
830 ms |
58452 KB |
Output is correct |
9 |
Correct |
760 ms |
57836 KB |
Output is correct |
10 |
Correct |
638 ms |
62184 KB |
Output is correct |
11 |
Correct |
329 ms |
47236 KB |
Output is correct |
12 |
Correct |
757 ms |
57632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
789 ms |
60088 KB |
Output is correct |
2 |
Correct |
782 ms |
60456 KB |
Output is correct |
3 |
Correct |
791 ms |
58672 KB |
Output is correct |
4 |
Correct |
760 ms |
58420 KB |
Output is correct |
5 |
Correct |
738 ms |
59436 KB |
Output is correct |
6 |
Correct |
735 ms |
67104 KB |
Output is correct |
7 |
Correct |
771 ms |
66408 KB |
Output is correct |
8 |
Correct |
810 ms |
60960 KB |
Output is correct |
9 |
Correct |
729 ms |
59348 KB |
Output is correct |
10 |
Correct |
727 ms |
58716 KB |
Output is correct |
11 |
Correct |
331 ms |
52136 KB |
Output is correct |
12 |
Correct |
747 ms |
68044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
15436 KB |
Output is correct |
2 |
Correct |
7 ms |
12204 KB |
Output is correct |
3 |
Correct |
8 ms |
12196 KB |
Output is correct |
4 |
Correct |
25 ms |
18124 KB |
Output is correct |
5 |
Correct |
17 ms |
15036 KB |
Output is correct |
6 |
Correct |
10 ms |
12200 KB |
Output is correct |
7 |
Correct |
10 ms |
12364 KB |
Output is correct |
8 |
Correct |
10 ms |
12456 KB |
Output is correct |
9 |
Correct |
10 ms |
12236 KB |
Output is correct |
10 |
Correct |
19 ms |
15124 KB |
Output is correct |
11 |
Correct |
8 ms |
12060 KB |
Output is correct |
12 |
Correct |
8 ms |
12108 KB |
Output is correct |
13 |
Correct |
8 ms |
12108 KB |
Output is correct |
14 |
Correct |
9 ms |
12200 KB |
Output is correct |
15 |
Correct |
9 ms |
12236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
806 ms |
59232 KB |
Output is correct |
2 |
Correct |
773 ms |
57980 KB |
Output is correct |
3 |
Correct |
815 ms |
68608 KB |
Output is correct |
4 |
Correct |
757 ms |
59208 KB |
Output is correct |
5 |
Correct |
762 ms |
59984 KB |
Output is correct |
6 |
Correct |
775 ms |
59440 KB |
Output is correct |
7 |
Correct |
747 ms |
59716 KB |
Output is correct |
8 |
Correct |
830 ms |
58452 KB |
Output is correct |
9 |
Correct |
760 ms |
57836 KB |
Output is correct |
10 |
Correct |
638 ms |
62184 KB |
Output is correct |
11 |
Correct |
329 ms |
47236 KB |
Output is correct |
12 |
Correct |
757 ms |
57632 KB |
Output is correct |
13 |
Correct |
789 ms |
60088 KB |
Output is correct |
14 |
Correct |
782 ms |
60456 KB |
Output is correct |
15 |
Correct |
791 ms |
58672 KB |
Output is correct |
16 |
Correct |
760 ms |
58420 KB |
Output is correct |
17 |
Correct |
738 ms |
59436 KB |
Output is correct |
18 |
Correct |
735 ms |
67104 KB |
Output is correct |
19 |
Correct |
771 ms |
66408 KB |
Output is correct |
20 |
Correct |
810 ms |
60960 KB |
Output is correct |
21 |
Correct |
729 ms |
59348 KB |
Output is correct |
22 |
Correct |
727 ms |
58716 KB |
Output is correct |
23 |
Correct |
331 ms |
52136 KB |
Output is correct |
24 |
Correct |
747 ms |
68044 KB |
Output is correct |
25 |
Correct |
18 ms |
15436 KB |
Output is correct |
26 |
Correct |
7 ms |
12204 KB |
Output is correct |
27 |
Correct |
8 ms |
12196 KB |
Output is correct |
28 |
Correct |
25 ms |
18124 KB |
Output is correct |
29 |
Correct |
17 ms |
15036 KB |
Output is correct |
30 |
Correct |
10 ms |
12200 KB |
Output is correct |
31 |
Correct |
10 ms |
12364 KB |
Output is correct |
32 |
Correct |
10 ms |
12456 KB |
Output is correct |
33 |
Correct |
10 ms |
12236 KB |
Output is correct |
34 |
Correct |
19 ms |
15124 KB |
Output is correct |
35 |
Correct |
8 ms |
12060 KB |
Output is correct |
36 |
Correct |
8 ms |
12108 KB |
Output is correct |
37 |
Correct |
8 ms |
12108 KB |
Output is correct |
38 |
Correct |
9 ms |
12200 KB |
Output is correct |
39 |
Correct |
9 ms |
12236 KB |
Output is correct |
40 |
Correct |
862 ms |
64216 KB |
Output is correct |
41 |
Correct |
722 ms |
58140 KB |
Output is correct |
42 |
Correct |
712 ms |
58084 KB |
Output is correct |
43 |
Correct |
388 ms |
52904 KB |
Output is correct |
44 |
Correct |
390 ms |
52820 KB |
Output is correct |
45 |
Correct |
807 ms |
64048 KB |
Output is correct |
46 |
Correct |
826 ms |
63748 KB |
Output is correct |
47 |
Correct |
766 ms |
59052 KB |
Output is correct |
48 |
Correct |
378 ms |
48932 KB |
Output is correct |
49 |
Correct |
667 ms |
63920 KB |
Output is correct |
50 |
Correct |
720 ms |
63276 KB |
Output is correct |
51 |
Correct |
744 ms |
67128 KB |
Output is correct |