//tavakol bar khoda
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)1e5 + 7;
const int MOD = (int)1e9 + 7;
const int infint = (int)1e8 + 3;
const ll inf = (ll)1e18;
ll n, m, distU[MAXN], distV[MAXN], distS[MAXN], S, T, U, V, visited[MAXN], dp[MAXN], way[MAXN];
vector<pair<ll, ll> > G[MAXN];
vector<int> dag[MAXN], topol;
void dijkstraU()
{
for (int i = 1; i <= n; i++)
distU[i] = inf;
distU[U] = 0;
set<pair<ll, ll> > S;
for (int i = 1; i <= n; i++)
S.insert({distU[i], i});
while(S.size())
{
pair<ll, ll> P = *S.begin();
S.erase(P);
for (auto v : G[P.second])
if(distU[v.first] > P.first + v.second)
{
S.erase({distU[v.first], v.first});
distU[v.first] = P.first + v.second;
S.insert({distU[v.first], v.first});
}
}
}
void dijkstraV()
{
for (int i = 1; i <= n; i++)
distV[i] = inf;
distV[V] = 0;
set<pair<ll, ll> > S;
for (int i = 1; i <= n; i++)
S.insert({distV[i], i});
while(S.size())
{
pair<ll, ll> P = *S.begin();
S.erase(P);
for (auto v : G[P.second])
if(distV[v.first] > P.first + v.second)
{
S.erase({distV[v.first], v.first});
distV[v.first] = P.first + v.second;
S.insert({distV[v.first], v.first});
}
}
}
void dijkstraS()
{
for (int i = 1; i <= n; i++)
distS[i] = inf;
distS[S] = 0;
set<pair<ll, ll> > S;
for (int i = 1; i <= n; i++)
S.insert({distS[i], i});
while(S.size())
{
pair<ll, ll> P = *S.begin();
S.erase(P);
for (auto v : G[P.second])
if(distS[v.first] > P.first + v.second)
{
S.erase({distS[v.first], v.first});
distS[v.first] = P.first + v.second;
S.insert({distS[v.first], v.first});
}
}
}
void dfs(int u)
{
visited[u] = 1;
for (auto v : dag[u])
if(!visited[v])
dfs(v);
topol.push_back(u);
}
void DFS(int u)
{
way[u] = 1;
for (auto v : dag[u])
if(!way[v])
DFS(v);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
cin >> S >> T >> U >> V;
for (int i = 0; i < m; i++)
{
ll a, b, w;
cin >> a >> b >> w;
G[a].push_back({b, w});
G[b].push_back({a, w});
}
dijkstraU();
dijkstraV();
dijkstraS();
for (int i = 1; i <= n; i++)
for (auto u : G[i])
if(distS[i] + u.second == distS[u.first])
dag[u.first].push_back(i);
DFS(T);
for (int i = 1; i <= n; i++)
dag[i].clear();
memset(visited, 0, sizeof visited);
for (int i = 1; i <= n; i++)
for (auto u : G[i])
if(distS[i] + u.second == distS[u.first] && way[u.first])
dag[i].push_back(u.first);
for (int i = 1; i <= n; i++)
if(!visited[i])
dfs(i);
reverse(topol.begin(), topol.end());
ll ans = distU[V];
for (int i = topol.size() - 1; i >= 0; i--)
{
int u = topol[i];
dp[u] = distV[u];
for (auto v : dag[u])
dp[u] = min(dp[u], dp[v]);
ans = min(ans, distU[u] + dp[u]);
}
for (int i = 1; i <= n; i++)
dag[i].clear();
topol.clear();
memset(visited, 0, sizeof visited);
for (int i = 1; i <= n; i++)
for (auto u : G[i])
if(distS[i] + u.second == distS[u.first] && way[u.first])
dag[u.first].push_back(i);
for (int i = 1; i <= n; i++)
if(!visited[i])
dfs(i);
reverse(topol.begin(), topol.end());
for (int i = topol.size() - 1; i >= 0; i--)
{
int u = topol[i];
dp[u] = distV[u];
for (auto v : dag[u])
dp[u] = min(dp[u], dp[v]);
ans = min(ans, distU[u] + dp[u]);
}
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1000 ms |
29432 KB |
Output is correct |
2 |
Correct |
953 ms |
33948 KB |
Output is correct |
3 |
Correct |
782 ms |
39676 KB |
Output is correct |
4 |
Correct |
830 ms |
40504 KB |
Output is correct |
5 |
Correct |
834 ms |
44844 KB |
Output is correct |
6 |
Correct |
1074 ms |
48156 KB |
Output is correct |
7 |
Correct |
1008 ms |
52244 KB |
Output is correct |
8 |
Correct |
985 ms |
55796 KB |
Output is correct |
9 |
Correct |
959 ms |
59484 KB |
Output is correct |
10 |
Correct |
750 ms |
63724 KB |
Output is correct |
11 |
Correct |
604 ms |
63724 KB |
Output is correct |
12 |
Correct |
824 ms |
70372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
882 ms |
75916 KB |
Output is correct |
2 |
Correct |
867 ms |
79212 KB |
Output is correct |
3 |
Correct |
868 ms |
82696 KB |
Output is correct |
4 |
Correct |
883 ms |
86408 KB |
Output is correct |
5 |
Correct |
837 ms |
89660 KB |
Output is correct |
6 |
Correct |
809 ms |
94536 KB |
Output is correct |
7 |
Correct |
957 ms |
97992 KB |
Output is correct |
8 |
Correct |
976 ms |
100032 KB |
Output is correct |
9 |
Correct |
982 ms |
103768 KB |
Output is correct |
10 |
Correct |
918 ms |
107260 KB |
Output is correct |
11 |
Correct |
657 ms |
107260 KB |
Output is correct |
12 |
Correct |
967 ms |
114012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
114012 KB |
Output is correct |
2 |
Correct |
7 ms |
114012 KB |
Output is correct |
3 |
Correct |
7 ms |
114012 KB |
Output is correct |
4 |
Correct |
24 ms |
114012 KB |
Output is correct |
5 |
Correct |
15 ms |
114012 KB |
Output is correct |
6 |
Correct |
8 ms |
114012 KB |
Output is correct |
7 |
Correct |
8 ms |
114012 KB |
Output is correct |
8 |
Correct |
8 ms |
114012 KB |
Output is correct |
9 |
Correct |
8 ms |
114012 KB |
Output is correct |
10 |
Correct |
15 ms |
114012 KB |
Output is correct |
11 |
Correct |
6 ms |
114012 KB |
Output is correct |
12 |
Correct |
7 ms |
114012 KB |
Output is correct |
13 |
Correct |
7 ms |
114012 KB |
Output is correct |
14 |
Correct |
7 ms |
114012 KB |
Output is correct |
15 |
Correct |
7 ms |
114012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1000 ms |
29432 KB |
Output is correct |
2 |
Correct |
953 ms |
33948 KB |
Output is correct |
3 |
Correct |
782 ms |
39676 KB |
Output is correct |
4 |
Correct |
830 ms |
40504 KB |
Output is correct |
5 |
Correct |
834 ms |
44844 KB |
Output is correct |
6 |
Correct |
1074 ms |
48156 KB |
Output is correct |
7 |
Correct |
1008 ms |
52244 KB |
Output is correct |
8 |
Correct |
985 ms |
55796 KB |
Output is correct |
9 |
Correct |
959 ms |
59484 KB |
Output is correct |
10 |
Correct |
750 ms |
63724 KB |
Output is correct |
11 |
Correct |
604 ms |
63724 KB |
Output is correct |
12 |
Correct |
824 ms |
70372 KB |
Output is correct |
13 |
Correct |
882 ms |
75916 KB |
Output is correct |
14 |
Correct |
867 ms |
79212 KB |
Output is correct |
15 |
Correct |
868 ms |
82696 KB |
Output is correct |
16 |
Correct |
883 ms |
86408 KB |
Output is correct |
17 |
Correct |
837 ms |
89660 KB |
Output is correct |
18 |
Correct |
809 ms |
94536 KB |
Output is correct |
19 |
Correct |
957 ms |
97992 KB |
Output is correct |
20 |
Correct |
976 ms |
100032 KB |
Output is correct |
21 |
Correct |
982 ms |
103768 KB |
Output is correct |
22 |
Correct |
918 ms |
107260 KB |
Output is correct |
23 |
Correct |
657 ms |
107260 KB |
Output is correct |
24 |
Correct |
967 ms |
114012 KB |
Output is correct |
25 |
Correct |
16 ms |
114012 KB |
Output is correct |
26 |
Correct |
7 ms |
114012 KB |
Output is correct |
27 |
Correct |
7 ms |
114012 KB |
Output is correct |
28 |
Correct |
24 ms |
114012 KB |
Output is correct |
29 |
Correct |
15 ms |
114012 KB |
Output is correct |
30 |
Correct |
8 ms |
114012 KB |
Output is correct |
31 |
Correct |
8 ms |
114012 KB |
Output is correct |
32 |
Correct |
8 ms |
114012 KB |
Output is correct |
33 |
Correct |
8 ms |
114012 KB |
Output is correct |
34 |
Correct |
15 ms |
114012 KB |
Output is correct |
35 |
Correct |
6 ms |
114012 KB |
Output is correct |
36 |
Correct |
7 ms |
114012 KB |
Output is correct |
37 |
Correct |
7 ms |
114012 KB |
Output is correct |
38 |
Correct |
7 ms |
114012 KB |
Output is correct |
39 |
Correct |
7 ms |
114012 KB |
Output is correct |
40 |
Correct |
965 ms |
116912 KB |
Output is correct |
41 |
Correct |
1113 ms |
121812 KB |
Output is correct |
42 |
Correct |
859 ms |
126028 KB |
Output is correct |
43 |
Correct |
496 ms |
126308 KB |
Output is correct |
44 |
Correct |
507 ms |
128168 KB |
Output is correct |
45 |
Correct |
879 ms |
134636 KB |
Output is correct |
46 |
Correct |
927 ms |
137836 KB |
Output is correct |
47 |
Correct |
1022 ms |
141288 KB |
Output is correct |
48 |
Correct |
636 ms |
141288 KB |
Output is correct |
49 |
Correct |
777 ms |
145364 KB |
Output is correct |
50 |
Correct |
1030 ms |
150448 KB |
Output is correct |
51 |
Correct |
1046 ms |
153968 KB |
Output is correct |