#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct edge{
int v, w;
edge(int v=0,int w=0): v(v), w(w) {}
};
int n,m,s,t,u,v;
vector <edge> G[100005];
vector <int> dag[100005];
ll dis[100005], disS[100005], disU[100005], disV[100005];
bool visited[100005];
priority_queue <pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long, int> > > pq;
void dijkstra(int root){
fill(dis+1,dis+n+1, (ll) 1e18);
fill(visited,visited+n+1,0);
dis[root] = 0;
pq.push(pair<ll,int>(0ll, root));
while(pq.size()){
int u = pq.top().second;
pq.pop();
if (visited[u]) continue;
visited[u] = 1;
for(auto v: G[u]){
if (dis[v.v] > dis[u] + v.w)
dis[v.v] = dis[u] + v.w,
pq.push(pair<ll,int>(dis[v.v], v.v));
}
}
}
void trailBack(int u){
if (visited[u]) return;
visited[u] = 1;
for(auto v: G[u]){
if (disS[v.v] == disS[u] - v.w)
dag[v.v].push_back(u),
trailBack(v.v);
}
}
ll ans = (ll) 1e18;
ll value[100005];
void dfs(int u){
value[u] = (ll) disV[u];
for(int v: dag[u]){
if (value[v] == -1) dfs(v);
value[u] = min(value[u], value[v]);
}
ans = min(ans, disU[u] + value[u]);
}
int main(){
iostream::sync_with_stdio(0);
cin >> n >> m >> s >> t >> u >> v;
for(int i=1;i<=m;i++){
int a,b,c;
cin >> a >> b >> c;
G[a].push_back(edge(b, c));
G[b].push_back(edge(a, c));
}
dijkstra(s);
for(int i=1;i<=n;i++) disS[i] = dis[i];
fill(visited+1,visited+n+1,0);
trailBack(t);
dijkstra(u);
for(int i=1;i<=n;i++) disU[i] = dis[i];
ans = disU[v];
dijkstra(v);
for(int i=1;i<=n;i++) disV[i] = dis[i];
fill(value+1,value+1+n,-1);
dfs(s);
swap(disU, disV);
fill(value+1,value+1+n,-1);
dfs(s);
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
294 ms |
16612 KB |
Output is correct |
2 |
Correct |
342 ms |
16956 KB |
Output is correct |
3 |
Correct |
348 ms |
24720 KB |
Output is correct |
4 |
Correct |
301 ms |
24720 KB |
Output is correct |
5 |
Correct |
331 ms |
28696 KB |
Output is correct |
6 |
Correct |
311 ms |
31780 KB |
Output is correct |
7 |
Correct |
347 ms |
36504 KB |
Output is correct |
8 |
Correct |
337 ms |
39768 KB |
Output is correct |
9 |
Correct |
305 ms |
42504 KB |
Output is correct |
10 |
Correct |
250 ms |
46936 KB |
Output is correct |
11 |
Correct |
110 ms |
48328 KB |
Output is correct |
12 |
Correct |
320 ms |
53412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
335 ms |
55164 KB |
Output is correct |
2 |
Correct |
332 ms |
55440 KB |
Output is correct |
3 |
Correct |
346 ms |
55440 KB |
Output is correct |
4 |
Correct |
344 ms |
55440 KB |
Output is correct |
5 |
Correct |
350 ms |
55824 KB |
Output is correct |
6 |
Correct |
355 ms |
57380 KB |
Output is correct |
7 |
Correct |
378 ms |
58132 KB |
Output is correct |
8 |
Correct |
371 ms |
58132 KB |
Output is correct |
9 |
Correct |
360 ms |
58132 KB |
Output is correct |
10 |
Correct |
360 ms |
58132 KB |
Output is correct |
11 |
Correct |
150 ms |
58132 KB |
Output is correct |
12 |
Correct |
381 ms |
58132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
58132 KB |
Output is correct |
2 |
Correct |
7 ms |
58132 KB |
Output is correct |
3 |
Correct |
7 ms |
58132 KB |
Output is correct |
4 |
Correct |
23 ms |
58132 KB |
Output is correct |
5 |
Correct |
15 ms |
58132 KB |
Output is correct |
6 |
Correct |
8 ms |
58132 KB |
Output is correct |
7 |
Correct |
9 ms |
58132 KB |
Output is correct |
8 |
Correct |
9 ms |
58132 KB |
Output is correct |
9 |
Correct |
8 ms |
58132 KB |
Output is correct |
10 |
Correct |
16 ms |
58132 KB |
Output is correct |
11 |
Correct |
8 ms |
58132 KB |
Output is correct |
12 |
Correct |
7 ms |
58132 KB |
Output is correct |
13 |
Correct |
7 ms |
58132 KB |
Output is correct |
14 |
Correct |
9 ms |
58132 KB |
Output is correct |
15 |
Correct |
8 ms |
58132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
294 ms |
16612 KB |
Output is correct |
2 |
Correct |
342 ms |
16956 KB |
Output is correct |
3 |
Correct |
348 ms |
24720 KB |
Output is correct |
4 |
Correct |
301 ms |
24720 KB |
Output is correct |
5 |
Correct |
331 ms |
28696 KB |
Output is correct |
6 |
Correct |
311 ms |
31780 KB |
Output is correct |
7 |
Correct |
347 ms |
36504 KB |
Output is correct |
8 |
Correct |
337 ms |
39768 KB |
Output is correct |
9 |
Correct |
305 ms |
42504 KB |
Output is correct |
10 |
Correct |
250 ms |
46936 KB |
Output is correct |
11 |
Correct |
110 ms |
48328 KB |
Output is correct |
12 |
Correct |
320 ms |
53412 KB |
Output is correct |
13 |
Correct |
335 ms |
55164 KB |
Output is correct |
14 |
Correct |
332 ms |
55440 KB |
Output is correct |
15 |
Correct |
346 ms |
55440 KB |
Output is correct |
16 |
Correct |
344 ms |
55440 KB |
Output is correct |
17 |
Correct |
350 ms |
55824 KB |
Output is correct |
18 |
Correct |
355 ms |
57380 KB |
Output is correct |
19 |
Correct |
378 ms |
58132 KB |
Output is correct |
20 |
Correct |
371 ms |
58132 KB |
Output is correct |
21 |
Correct |
360 ms |
58132 KB |
Output is correct |
22 |
Correct |
360 ms |
58132 KB |
Output is correct |
23 |
Correct |
150 ms |
58132 KB |
Output is correct |
24 |
Correct |
381 ms |
58132 KB |
Output is correct |
25 |
Correct |
16 ms |
58132 KB |
Output is correct |
26 |
Correct |
7 ms |
58132 KB |
Output is correct |
27 |
Correct |
7 ms |
58132 KB |
Output is correct |
28 |
Correct |
23 ms |
58132 KB |
Output is correct |
29 |
Correct |
15 ms |
58132 KB |
Output is correct |
30 |
Correct |
8 ms |
58132 KB |
Output is correct |
31 |
Correct |
9 ms |
58132 KB |
Output is correct |
32 |
Correct |
9 ms |
58132 KB |
Output is correct |
33 |
Correct |
8 ms |
58132 KB |
Output is correct |
34 |
Correct |
16 ms |
58132 KB |
Output is correct |
35 |
Correct |
8 ms |
58132 KB |
Output is correct |
36 |
Correct |
7 ms |
58132 KB |
Output is correct |
37 |
Correct |
7 ms |
58132 KB |
Output is correct |
38 |
Correct |
9 ms |
58132 KB |
Output is correct |
39 |
Correct |
8 ms |
58132 KB |
Output is correct |
40 |
Correct |
292 ms |
59624 KB |
Output is correct |
41 |
Correct |
307 ms |
63872 KB |
Output is correct |
42 |
Correct |
353 ms |
68064 KB |
Output is correct |
43 |
Correct |
141 ms |
71464 KB |
Output is correct |
44 |
Correct |
173 ms |
73700 KB |
Output is correct |
45 |
Correct |
402 ms |
78064 KB |
Output is correct |
46 |
Correct |
377 ms |
81316 KB |
Output is correct |
47 |
Correct |
328 ms |
82944 KB |
Output is correct |
48 |
Correct |
170 ms |
84568 KB |
Output is correct |
49 |
Correct |
255 ms |
88448 KB |
Output is correct |
50 |
Correct |
375 ms |
93192 KB |
Output is correct |
51 |
Correct |
385 ms |
97436 KB |
Output is correct |