#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e5+5;
ll n, m, s, t, a, b, u, v, w, ans, dp[nx][2];
bool vs[nx];
vector<vector<pair<ll, ll>>> d(nx);
vector<ll> S(nx), A(nx), B(nx);
void dij(int u, vector<ll> &v)
{
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
for (int i=1; i<=n; i++) v[i]=1e16;
v[u]=0;
pq.push({0, u});
while (!pq.empty())
{
auto [cw, cl]=pq.top();
pq.pop();
for (auto [nl, nw]:d[cl])
{
if (v[nl]>cw+nw)
{
pq.push({cw+nw, nl});
v[nl]=cw+nw;
}
}
}
}
void dfs(int u)
{
if (vs[u]) return;
vs[u]=1;
dp[u][0]=A[u];
dp[u][1]=B[u];
for (auto [nl, nw]:d[u])
{
if (S[nl]+nw==S[u])
{
dfs(nl);
dp[u][0]=min(dp[u][0], dp[nl][0]);
dp[u][1]=min(dp[u][1], dp[nl][1]);
}
}
ans=min({ans, dp[u][0]+B[u], dp[u][1]+A[u]});
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m>>s>>t>>a>>b;
for (int i=0; i<m; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
dij(s, S);
dij(a, A);
dij(b, B);
for (int i=1; i<=n; i++) dp[i][0]=dp[i][1]=1e16;
ans=A[b];
dfs(t);
cout<<ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
162 ms |
18488 KB |
Output is correct |
2 |
Correct |
173 ms |
17376 KB |
Output is correct |
3 |
Correct |
196 ms |
22332 KB |
Output is correct |
4 |
Correct |
157 ms |
18456 KB |
Output is correct |
5 |
Correct |
155 ms |
17268 KB |
Output is correct |
6 |
Correct |
225 ms |
18600 KB |
Output is correct |
7 |
Correct |
210 ms |
17456 KB |
Output is correct |
8 |
Correct |
193 ms |
17356 KB |
Output is correct |
9 |
Correct |
201 ms |
17196 KB |
Output is correct |
10 |
Correct |
148 ms |
17064 KB |
Output is correct |
11 |
Correct |
64 ms |
15104 KB |
Output is correct |
12 |
Correct |
175 ms |
17160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
184 ms |
19384 KB |
Output is correct |
2 |
Correct |
191 ms |
19772 KB |
Output is correct |
3 |
Correct |
228 ms |
19244 KB |
Output is correct |
4 |
Correct |
198 ms |
19544 KB |
Output is correct |
5 |
Correct |
190 ms |
20112 KB |
Output is correct |
6 |
Correct |
213 ms |
21800 KB |
Output is correct |
7 |
Correct |
202 ms |
22296 KB |
Output is correct |
8 |
Correct |
190 ms |
19636 KB |
Output is correct |
9 |
Correct |
195 ms |
20044 KB |
Output is correct |
10 |
Correct |
228 ms |
19272 KB |
Output is correct |
11 |
Correct |
82 ms |
16788 KB |
Output is correct |
12 |
Correct |
182 ms |
22064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
6356 KB |
Output is correct |
2 |
Correct |
2 ms |
5076 KB |
Output is correct |
3 |
Correct |
2 ms |
5076 KB |
Output is correct |
4 |
Correct |
14 ms |
7824 KB |
Output is correct |
5 |
Correct |
7 ms |
6356 KB |
Output is correct |
6 |
Correct |
3 ms |
5084 KB |
Output is correct |
7 |
Correct |
3 ms |
5076 KB |
Output is correct |
8 |
Correct |
3 ms |
5204 KB |
Output is correct |
9 |
Correct |
3 ms |
5076 KB |
Output is correct |
10 |
Correct |
7 ms |
6356 KB |
Output is correct |
11 |
Correct |
2 ms |
5076 KB |
Output is correct |
12 |
Correct |
2 ms |
4948 KB |
Output is correct |
13 |
Correct |
2 ms |
5076 KB |
Output is correct |
14 |
Correct |
2 ms |
5076 KB |
Output is correct |
15 |
Correct |
3 ms |
5076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
162 ms |
18488 KB |
Output is correct |
2 |
Correct |
173 ms |
17376 KB |
Output is correct |
3 |
Correct |
196 ms |
22332 KB |
Output is correct |
4 |
Correct |
157 ms |
18456 KB |
Output is correct |
5 |
Correct |
155 ms |
17268 KB |
Output is correct |
6 |
Correct |
225 ms |
18600 KB |
Output is correct |
7 |
Correct |
210 ms |
17456 KB |
Output is correct |
8 |
Correct |
193 ms |
17356 KB |
Output is correct |
9 |
Correct |
201 ms |
17196 KB |
Output is correct |
10 |
Correct |
148 ms |
17064 KB |
Output is correct |
11 |
Correct |
64 ms |
15104 KB |
Output is correct |
12 |
Correct |
175 ms |
17160 KB |
Output is correct |
13 |
Correct |
184 ms |
19384 KB |
Output is correct |
14 |
Correct |
191 ms |
19772 KB |
Output is correct |
15 |
Correct |
228 ms |
19244 KB |
Output is correct |
16 |
Correct |
198 ms |
19544 KB |
Output is correct |
17 |
Correct |
190 ms |
20112 KB |
Output is correct |
18 |
Correct |
213 ms |
21800 KB |
Output is correct |
19 |
Correct |
202 ms |
22296 KB |
Output is correct |
20 |
Correct |
190 ms |
19636 KB |
Output is correct |
21 |
Correct |
195 ms |
20044 KB |
Output is correct |
22 |
Correct |
228 ms |
19272 KB |
Output is correct |
23 |
Correct |
82 ms |
16788 KB |
Output is correct |
24 |
Correct |
182 ms |
22064 KB |
Output is correct |
25 |
Correct |
7 ms |
6356 KB |
Output is correct |
26 |
Correct |
2 ms |
5076 KB |
Output is correct |
27 |
Correct |
2 ms |
5076 KB |
Output is correct |
28 |
Correct |
14 ms |
7824 KB |
Output is correct |
29 |
Correct |
7 ms |
6356 KB |
Output is correct |
30 |
Correct |
3 ms |
5084 KB |
Output is correct |
31 |
Correct |
3 ms |
5076 KB |
Output is correct |
32 |
Correct |
3 ms |
5204 KB |
Output is correct |
33 |
Correct |
3 ms |
5076 KB |
Output is correct |
34 |
Correct |
7 ms |
6356 KB |
Output is correct |
35 |
Correct |
2 ms |
5076 KB |
Output is correct |
36 |
Correct |
2 ms |
4948 KB |
Output is correct |
37 |
Correct |
2 ms |
5076 KB |
Output is correct |
38 |
Correct |
2 ms |
5076 KB |
Output is correct |
39 |
Correct |
3 ms |
5076 KB |
Output is correct |
40 |
Correct |
208 ms |
18088 KB |
Output is correct |
41 |
Correct |
193 ms |
17264 KB |
Output is correct |
42 |
Correct |
164 ms |
17284 KB |
Output is correct |
43 |
Correct |
66 ms |
15848 KB |
Output is correct |
44 |
Correct |
72 ms |
15760 KB |
Output is correct |
45 |
Correct |
155 ms |
17956 KB |
Output is correct |
46 |
Correct |
157 ms |
17172 KB |
Output is correct |
47 |
Correct |
184 ms |
18428 KB |
Output is correct |
48 |
Correct |
69 ms |
13260 KB |
Output is correct |
49 |
Correct |
145 ms |
18104 KB |
Output is correct |
50 |
Correct |
215 ms |
17196 KB |
Output is correct |
51 |
Correct |
168 ms |
17280 KB |
Output is correct |