// In the name of Allah. Ya ali!
#include<bits/stdc++.h>
#define double long double
typedef long long ll;
const ll MAX_N = 1e5+10;
const ll MOD = 1e9+7;
using namespace std;
vector<pair<int,int>> g[MAX_N];
vector<int> g2[MAX_N];
vector<int> p[MAX_N];
ll dis[MAX_N];
ll m1[MAX_N];
ll d1[MAX_N];
ll d2[MAX_N];
ll m2[MAX_N];
int mark[MAX_N];
bool done[MAX_N];
int n,m,s,t,u,v;
ll ans = 1e18;
void dij(int start)
{
for(int i = 1;i<=n;++i)
dis[i] = 1e18;
dis[start] = 0;
set<pair<ll,int>> st;
for(int i = 1;i<=n;++i)
st.insert({dis[i],i});
while(st.size())
{
int v = (*st.begin()).second;
st.erase(st.begin());
for(auto x:g[v])
{
int u = x.first;
ll d = dis[v]+x.second;
if (dis[u]==d)
p[u].push_back(v);
else if (dis[u]>d)
{
p[u].clear();
p[u].push_back(v);
st.erase({dis[u],u});
dis[u] = d;
st.insert({dis[u],u});
}
}
}
}
void dfs(int v)
{
mark[v]++;
for(auto x:g2[v])
{
if (!mark[x])
dfs(x);
m1[v] = min(m1[v],m1[x]);
m2[v] = min(m2[v],m2[x]);
}
ans = min(ans,min(m1[v]+d2[v],m2[v]+d1[v]));
}
void addedges(int v)
{
done[v] = true;
for(auto x:p[v])
{
g2[x].push_back(v);
if (!done[x])
addedges(x);
}
}
int main()
{
cin >> n >> m >> s >> t >> u >> v;
for(int i = 1;i<=m;++i)
{
int u,v,w;
cin >> u >> v >> w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dij(s);
addedges(t);
dij(u);
for(int i = 1;i<=n;++i)
d1[i] = m1[i] = dis[i];
dij(v);
for(int i = 1;i<=n;++i)
d2[i] = m2[i] = dis[i];
ans = dis[u];
dfs(s);
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1712 ms |
26444 KB |
Output is correct |
2 |
Correct |
1488 ms |
28152 KB |
Output is correct |
3 |
Correct |
1381 ms |
33244 KB |
Output is correct |
4 |
Correct |
1551 ms |
26616 KB |
Output is correct |
5 |
Correct |
1240 ms |
28796 KB |
Output is correct |
6 |
Correct |
1489 ms |
26616 KB |
Output is correct |
7 |
Correct |
1376 ms |
29176 KB |
Output is correct |
8 |
Correct |
1238 ms |
29204 KB |
Output is correct |
9 |
Correct |
1247 ms |
26596 KB |
Output is correct |
10 |
Correct |
1215 ms |
26764 KB |
Output is correct |
11 |
Correct |
813 ms |
28280 KB |
Output is correct |
12 |
Correct |
1303 ms |
26872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1444 ms |
29432 KB |
Output is correct |
2 |
Correct |
1566 ms |
29992 KB |
Output is correct |
3 |
Correct |
1517 ms |
29432 KB |
Output is correct |
4 |
Correct |
1472 ms |
29976 KB |
Output is correct |
5 |
Correct |
1400 ms |
30584 KB |
Output is correct |
6 |
Correct |
1430 ms |
32504 KB |
Output is correct |
7 |
Correct |
1627 ms |
33288 KB |
Output is correct |
8 |
Correct |
1635 ms |
29956 KB |
Output is correct |
9 |
Correct |
1718 ms |
30548 KB |
Output is correct |
10 |
Correct |
1607 ms |
29468 KB |
Output is correct |
11 |
Correct |
824 ms |
30220 KB |
Output is correct |
12 |
Correct |
1380 ms |
33016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
37 ms |
8232 KB |
Output is correct |
2 |
Correct |
11 ms |
7396 KB |
Output is correct |
3 |
Correct |
10 ms |
7424 KB |
Output is correct |
4 |
Correct |
53 ms |
9592 KB |
Output is correct |
5 |
Correct |
32 ms |
8448 KB |
Output is correct |
6 |
Correct |
11 ms |
7424 KB |
Output is correct |
7 |
Correct |
12 ms |
7552 KB |
Output is correct |
8 |
Correct |
14 ms |
7552 KB |
Output is correct |
9 |
Correct |
12 ms |
7588 KB |
Output is correct |
10 |
Correct |
37 ms |
8572 KB |
Output is correct |
11 |
Correct |
12 ms |
7424 KB |
Output is correct |
12 |
Correct |
10 ms |
7552 KB |
Output is correct |
13 |
Correct |
10 ms |
7424 KB |
Output is correct |
14 |
Correct |
11 ms |
7424 KB |
Output is correct |
15 |
Correct |
11 ms |
7624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1712 ms |
26444 KB |
Output is correct |
2 |
Correct |
1488 ms |
28152 KB |
Output is correct |
3 |
Correct |
1381 ms |
33244 KB |
Output is correct |
4 |
Correct |
1551 ms |
26616 KB |
Output is correct |
5 |
Correct |
1240 ms |
28796 KB |
Output is correct |
6 |
Correct |
1489 ms |
26616 KB |
Output is correct |
7 |
Correct |
1376 ms |
29176 KB |
Output is correct |
8 |
Correct |
1238 ms |
29204 KB |
Output is correct |
9 |
Correct |
1247 ms |
26596 KB |
Output is correct |
10 |
Correct |
1215 ms |
26764 KB |
Output is correct |
11 |
Correct |
813 ms |
28280 KB |
Output is correct |
12 |
Correct |
1303 ms |
26872 KB |
Output is correct |
13 |
Correct |
1444 ms |
29432 KB |
Output is correct |
14 |
Correct |
1566 ms |
29992 KB |
Output is correct |
15 |
Correct |
1517 ms |
29432 KB |
Output is correct |
16 |
Correct |
1472 ms |
29976 KB |
Output is correct |
17 |
Correct |
1400 ms |
30584 KB |
Output is correct |
18 |
Correct |
1430 ms |
32504 KB |
Output is correct |
19 |
Correct |
1627 ms |
33288 KB |
Output is correct |
20 |
Correct |
1635 ms |
29956 KB |
Output is correct |
21 |
Correct |
1718 ms |
30548 KB |
Output is correct |
22 |
Correct |
1607 ms |
29468 KB |
Output is correct |
23 |
Correct |
824 ms |
30220 KB |
Output is correct |
24 |
Correct |
1380 ms |
33016 KB |
Output is correct |
25 |
Correct |
37 ms |
8232 KB |
Output is correct |
26 |
Correct |
11 ms |
7396 KB |
Output is correct |
27 |
Correct |
10 ms |
7424 KB |
Output is correct |
28 |
Correct |
53 ms |
9592 KB |
Output is correct |
29 |
Correct |
32 ms |
8448 KB |
Output is correct |
30 |
Correct |
11 ms |
7424 KB |
Output is correct |
31 |
Correct |
12 ms |
7552 KB |
Output is correct |
32 |
Correct |
14 ms |
7552 KB |
Output is correct |
33 |
Correct |
12 ms |
7588 KB |
Output is correct |
34 |
Correct |
37 ms |
8572 KB |
Output is correct |
35 |
Correct |
12 ms |
7424 KB |
Output is correct |
36 |
Correct |
10 ms |
7552 KB |
Output is correct |
37 |
Correct |
10 ms |
7424 KB |
Output is correct |
38 |
Correct |
11 ms |
7424 KB |
Output is correct |
39 |
Correct |
11 ms |
7624 KB |
Output is correct |
40 |
Correct |
1236 ms |
30024 KB |
Output is correct |
41 |
Correct |
1437 ms |
30576 KB |
Output is correct |
42 |
Correct |
1368 ms |
30556 KB |
Output is correct |
43 |
Correct |
801 ms |
32824 KB |
Output is correct |
44 |
Correct |
840 ms |
32920 KB |
Output is correct |
45 |
Correct |
1253 ms |
33872 KB |
Output is correct |
46 |
Correct |
1320 ms |
33900 KB |
Output is correct |
47 |
Correct |
1503 ms |
30904 KB |
Output is correct |
48 |
Correct |
789 ms |
30240 KB |
Output is correct |
49 |
Correct |
1122 ms |
30352 KB |
Output is correct |
50 |
Correct |
1300 ms |
33164 KB |
Output is correct |
51 |
Correct |
1290 ms |
34040 KB |
Output is correct |