#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
vector<in> adj[MX];
void dijsktra(int n, int src, vector<int> &dist)
{
priority_queue<in> pq;
dist.assign(n+1, INF);
pq.push({dist[src] = 0, src});
while(pq.size())
{
auto [wp, U] = pq.top(); wp = -wp; pq.pop();
if(dist[U] < wp)
continue;
for(auto [v, w]: adj[U])
{
if(dist[v] > (dist[U]+w))
{
dist[v] = dist[U]+w;
pq.push({-dist[v], v});
}
}
}
return;
}
signed main()
{
fast();
int n, m;
cin >> n >> m;
int S, T, U, V;
cin >> S >> T >> U >> V;
while(m--)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
vector<int> d1, d2;
dijsktra(n, U, d1); dijsktra(n, V, d2);
vector<int> dist; dist.assign(n+1, INF);
/*for(int i = 1; i <= n; i++)
cout << d1[i] << " ";
cout << endl;
for(int i = 1; i <= n; i++)
cout << d2[i] << " ";
cout << endl;*/
int cnt[4][n+1];
for(int i = 1; i <= n; i++)
{
for(int j = 1; j < 4; j++)
cnt[j][i] = INF;
}
cnt[1][S] = d1[S]; cnt[2][S] = d2[S]; cnt[3][S] = d1[S]+d2[S];
dist.assign(n+1, INF);
priority_queue<in> pq;
pq.push({dist[S] = 0, S});
while(pq.size())
{
auto [wp, u] = pq.top(); wp = -wp; pq.pop();
if(dist[u] < wp)
continue;
for(auto [v, w]: adj[u])
{
if(dist[v] > (dist[u]+w))
{
dist[v] = dist[u]+w;
pq.push({-dist[v], v});
cnt[1][v] = min(cnt[1][u], d1[v]);
cnt[2][v] = min(cnt[2][u], d2[v]);
cnt[3][v] = min(cnt[3][u], min(d1[v] + cnt[2][u], d2[v] + cnt[1][u]));
cnt[3][v] = min(cnt[3][v], d1[v]+d2[v]);
}
else if(dist[v] == (dist[u]+w))
{
cnt[1][v] = min(cnt[1][v], cnt[1][u]);
cnt[2][v] = min(cnt[2][v], cnt[2][u]);
cnt[3][v] = min(cnt[3][v], min(d1[v] + cnt[2][u], d2[v] + cnt[1][u]));
cnt[3][v] = min(cnt[3][v], cnt[3][u]);
}
}
}
int ans = min(d1[V], cnt[3][T]);
cout << ans << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
174 ms |
30316 KB |
Output is correct |
2 |
Correct |
184 ms |
28744 KB |
Output is correct |
3 |
Correct |
182 ms |
28476 KB |
Output is correct |
4 |
Correct |
205 ms |
29108 KB |
Output is correct |
5 |
Correct |
155 ms |
28512 KB |
Output is correct |
6 |
Correct |
179 ms |
31308 KB |
Output is correct |
7 |
Correct |
250 ms |
28648 KB |
Output is correct |
8 |
Correct |
196 ms |
28632 KB |
Output is correct |
9 |
Correct |
216 ms |
29784 KB |
Output is correct |
10 |
Correct |
161 ms |
29320 KB |
Output is correct |
11 |
Correct |
59 ms |
20180 KB |
Output is correct |
12 |
Correct |
209 ms |
29204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
197 ms |
29004 KB |
Output is correct |
2 |
Correct |
193 ms |
28564 KB |
Output is correct |
3 |
Correct |
204 ms |
28992 KB |
Output is correct |
4 |
Correct |
198 ms |
28680 KB |
Output is correct |
5 |
Correct |
203 ms |
28692 KB |
Output is correct |
6 |
Correct |
175 ms |
28644 KB |
Output is correct |
7 |
Correct |
177 ms |
28520 KB |
Output is correct |
8 |
Correct |
186 ms |
28760 KB |
Output is correct |
9 |
Correct |
235 ms |
28892 KB |
Output is correct |
10 |
Correct |
193 ms |
28724 KB |
Output is correct |
11 |
Correct |
62 ms |
20308 KB |
Output is correct |
12 |
Correct |
177 ms |
28624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
9052 KB |
Output is correct |
2 |
Correct |
2 ms |
7516 KB |
Output is correct |
3 |
Correct |
2 ms |
7516 KB |
Output is correct |
4 |
Correct |
13 ms |
10792 KB |
Output is correct |
5 |
Correct |
11 ms |
9052 KB |
Output is correct |
6 |
Correct |
2 ms |
7516 KB |
Output is correct |
7 |
Correct |
2 ms |
7516 KB |
Output is correct |
8 |
Correct |
3 ms |
7768 KB |
Output is correct |
9 |
Correct |
2 ms |
7516 KB |
Output is correct |
10 |
Correct |
7 ms |
9044 KB |
Output is correct |
11 |
Correct |
2 ms |
7768 KB |
Output is correct |
12 |
Correct |
2 ms |
7512 KB |
Output is correct |
13 |
Correct |
2 ms |
7516 KB |
Output is correct |
14 |
Correct |
2 ms |
7404 KB |
Output is correct |
15 |
Correct |
2 ms |
7516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
174 ms |
30316 KB |
Output is correct |
2 |
Correct |
184 ms |
28744 KB |
Output is correct |
3 |
Correct |
182 ms |
28476 KB |
Output is correct |
4 |
Correct |
205 ms |
29108 KB |
Output is correct |
5 |
Correct |
155 ms |
28512 KB |
Output is correct |
6 |
Correct |
179 ms |
31308 KB |
Output is correct |
7 |
Correct |
250 ms |
28648 KB |
Output is correct |
8 |
Correct |
196 ms |
28632 KB |
Output is correct |
9 |
Correct |
216 ms |
29784 KB |
Output is correct |
10 |
Correct |
161 ms |
29320 KB |
Output is correct |
11 |
Correct |
59 ms |
20180 KB |
Output is correct |
12 |
Correct |
209 ms |
29204 KB |
Output is correct |
13 |
Correct |
197 ms |
29004 KB |
Output is correct |
14 |
Correct |
193 ms |
28564 KB |
Output is correct |
15 |
Correct |
204 ms |
28992 KB |
Output is correct |
16 |
Correct |
198 ms |
28680 KB |
Output is correct |
17 |
Correct |
203 ms |
28692 KB |
Output is correct |
18 |
Correct |
175 ms |
28644 KB |
Output is correct |
19 |
Correct |
177 ms |
28520 KB |
Output is correct |
20 |
Correct |
186 ms |
28760 KB |
Output is correct |
21 |
Correct |
235 ms |
28892 KB |
Output is correct |
22 |
Correct |
193 ms |
28724 KB |
Output is correct |
23 |
Correct |
62 ms |
20308 KB |
Output is correct |
24 |
Correct |
177 ms |
28624 KB |
Output is correct |
25 |
Correct |
11 ms |
9052 KB |
Output is correct |
26 |
Correct |
2 ms |
7516 KB |
Output is correct |
27 |
Correct |
2 ms |
7516 KB |
Output is correct |
28 |
Correct |
13 ms |
10792 KB |
Output is correct |
29 |
Correct |
11 ms |
9052 KB |
Output is correct |
30 |
Correct |
2 ms |
7516 KB |
Output is correct |
31 |
Correct |
2 ms |
7516 KB |
Output is correct |
32 |
Correct |
3 ms |
7768 KB |
Output is correct |
33 |
Correct |
2 ms |
7516 KB |
Output is correct |
34 |
Correct |
7 ms |
9044 KB |
Output is correct |
35 |
Correct |
2 ms |
7768 KB |
Output is correct |
36 |
Correct |
2 ms |
7512 KB |
Output is correct |
37 |
Correct |
2 ms |
7516 KB |
Output is correct |
38 |
Correct |
2 ms |
7404 KB |
Output is correct |
39 |
Correct |
2 ms |
7516 KB |
Output is correct |
40 |
Correct |
162 ms |
30080 KB |
Output is correct |
41 |
Correct |
175 ms |
29312 KB |
Output is correct |
42 |
Correct |
175 ms |
29424 KB |
Output is correct |
43 |
Correct |
60 ms |
20304 KB |
Output is correct |
44 |
Correct |
74 ms |
20592 KB |
Output is correct |
45 |
Correct |
163 ms |
28320 KB |
Output is correct |
46 |
Correct |
163 ms |
28220 KB |
Output is correct |
47 |
Correct |
167 ms |
28736 KB |
Output is correct |
48 |
Correct |
71 ms |
19696 KB |
Output is correct |
49 |
Correct |
144 ms |
29820 KB |
Output is correct |
50 |
Correct |
180 ms |
28144 KB |
Output is correct |
51 |
Correct |
144 ms |
28208 KB |
Output is correct |