#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()
const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 1e6 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
ll dis[MAXN][4];
int n;
vii g[MAXN];
vi dag[MAXN], rv[MAXN], topo;
int indeg[MAXN];
bool ing[MAXN];
void dijkstra(int root, int id){
for(int i=1; i<=n; i++) dis[i][id] = INF;
dis[root][id] = 0;
set<pll> s;
for(int i=1; i<=n; i++) s.insert({dis[i][id], i});
while(!s.empty()){
ll d, u;
tie(d, u) = *s.begin();
s.erase(s.begin());
for(auto &x : g[u]){
int v = x.X;
ll nd = d + x.Y;
if(nd < dis[v][id]){
s.erase({dis[v][id], v});
dis[v][id] = nd;
s.insert({dis[v][id], v});
}
}
}
}
ll dp[MAXN], dp2[MAXN];
void solve(){
int m;
int s, t, u, v;
cin >> n >> m >> s >> t >> u >> v;
for(int i=0; i<m; i++){
int a, b, w;
cin >> a >> b >> w;
g[a].PB({b, w});
g[b].PB({a, w});
}
dijkstra(s, 0);
dijkstra(t, 1);
dijkstra(u, 2);
dijkstra(v, 3);
ll opt = INF, ans = INF;
for(int i=1; i<=n; i++) opt = min(opt, dis[i][0] + dis[i][1]), ans = min(ans, dis[i][2] + dis[i][3]);
for(int i=1; i<=n; i++) ing[i] = (dis[i][0] + dis[i][1] == opt);
for(int i=1; i<=n; i++){
for(auto &x : g[i]){
if(dis[i][0] + x.Y + dis[x.X][1] == opt){
dag[i].PB(x.X);
rv[x.X].PB(i);
indeg[x.X]++;
}
}
}
vi st;
for(int i=1; i<=n; i++){
if(!ing[i]) continue;
if(indeg[i] == 0) st.PB(i);
}
while(st.size()){
int cr = st.back();
st.PPB();
topo.PB(cr);
for(auto &x : dag[cr]) if(--indeg[x] == 0) st.PB(x);
}
for(int i=1; i<=n; i++) dp[i] = dis[i][2], dp2[i] = dis[i][3];
for(auto &x : topo) for(auto &y : rv[x]) dp[x] = min(dp[x], dp[y]);
reverse(all(topo));
for(auto &x : topo) for(auto &y : dag[x]) dp2[x] = min(dp2[x], dp2[y]);
reverse(all(topo));
for(int i=1; i<=n; i++) if(ing[i]) ans = min(ans, dp[i] + dp2[i]);
for(int i=1; i<=n; i++) dp[i] = dis[i][3], dp2[i] = dis[i][2];
for(auto &x : topo) for(auto &y : rv[x]) dp[x] = min(dp[x], dp[y]);
reverse(all(topo));
for(auto &x : topo) for(auto &y : dag[x]) dp2[x] = min(dp2[x], dp2[y]);
reverse(all(topo));
for(int i=1; i<=n; i++) if(ing[i]) ans = min(ans, dp[i] + dp2[i]);
cout << ans << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
527 ms |
102772 KB |
Output is correct |
2 |
Correct |
593 ms |
102496 KB |
Output is correct |
3 |
Correct |
585 ms |
102896 KB |
Output is correct |
4 |
Correct |
533 ms |
102752 KB |
Output is correct |
5 |
Correct |
505 ms |
102356 KB |
Output is correct |
6 |
Correct |
583 ms |
102748 KB |
Output is correct |
7 |
Correct |
544 ms |
102456 KB |
Output is correct |
8 |
Correct |
561 ms |
102636 KB |
Output is correct |
9 |
Correct |
512 ms |
103252 KB |
Output is correct |
10 |
Correct |
411 ms |
103508 KB |
Output is correct |
11 |
Correct |
345 ms |
98128 KB |
Output is correct |
12 |
Correct |
544 ms |
103252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
535 ms |
102740 KB |
Output is correct |
2 |
Correct |
561 ms |
102440 KB |
Output is correct |
3 |
Correct |
561 ms |
102608 KB |
Output is correct |
4 |
Correct |
588 ms |
102616 KB |
Output is correct |
5 |
Correct |
559 ms |
102460 KB |
Output is correct |
6 |
Correct |
533 ms |
102896 KB |
Output is correct |
7 |
Correct |
582 ms |
102736 KB |
Output is correct |
8 |
Correct |
655 ms |
102484 KB |
Output is correct |
9 |
Correct |
588 ms |
102440 KB |
Output is correct |
10 |
Correct |
578 ms |
102608 KB |
Output is correct |
11 |
Correct |
317 ms |
98332 KB |
Output is correct |
12 |
Correct |
584 ms |
102824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
81500 KB |
Output is correct |
2 |
Correct |
20 ms |
80476 KB |
Output is correct |
3 |
Correct |
19 ms |
80488 KB |
Output is correct |
4 |
Correct |
28 ms |
82524 KB |
Output is correct |
5 |
Correct |
22 ms |
81552 KB |
Output is correct |
6 |
Correct |
18 ms |
80476 KB |
Output is correct |
7 |
Correct |
20 ms |
80476 KB |
Output is correct |
8 |
Correct |
19 ms |
80476 KB |
Output is correct |
9 |
Correct |
18 ms |
80476 KB |
Output is correct |
10 |
Correct |
22 ms |
81708 KB |
Output is correct |
11 |
Correct |
18 ms |
80728 KB |
Output is correct |
12 |
Correct |
17 ms |
80476 KB |
Output is correct |
13 |
Correct |
17 ms |
80476 KB |
Output is correct |
14 |
Correct |
17 ms |
80476 KB |
Output is correct |
15 |
Correct |
18 ms |
80476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
527 ms |
102772 KB |
Output is correct |
2 |
Correct |
593 ms |
102496 KB |
Output is correct |
3 |
Correct |
585 ms |
102896 KB |
Output is correct |
4 |
Correct |
533 ms |
102752 KB |
Output is correct |
5 |
Correct |
505 ms |
102356 KB |
Output is correct |
6 |
Correct |
583 ms |
102748 KB |
Output is correct |
7 |
Correct |
544 ms |
102456 KB |
Output is correct |
8 |
Correct |
561 ms |
102636 KB |
Output is correct |
9 |
Correct |
512 ms |
103252 KB |
Output is correct |
10 |
Correct |
411 ms |
103508 KB |
Output is correct |
11 |
Correct |
345 ms |
98128 KB |
Output is correct |
12 |
Correct |
544 ms |
103252 KB |
Output is correct |
13 |
Correct |
535 ms |
102740 KB |
Output is correct |
14 |
Correct |
561 ms |
102440 KB |
Output is correct |
15 |
Correct |
561 ms |
102608 KB |
Output is correct |
16 |
Correct |
588 ms |
102616 KB |
Output is correct |
17 |
Correct |
559 ms |
102460 KB |
Output is correct |
18 |
Correct |
533 ms |
102896 KB |
Output is correct |
19 |
Correct |
582 ms |
102736 KB |
Output is correct |
20 |
Correct |
655 ms |
102484 KB |
Output is correct |
21 |
Correct |
588 ms |
102440 KB |
Output is correct |
22 |
Correct |
578 ms |
102608 KB |
Output is correct |
23 |
Correct |
317 ms |
98332 KB |
Output is correct |
24 |
Correct |
584 ms |
102824 KB |
Output is correct |
25 |
Correct |
22 ms |
81500 KB |
Output is correct |
26 |
Correct |
20 ms |
80476 KB |
Output is correct |
27 |
Correct |
19 ms |
80488 KB |
Output is correct |
28 |
Correct |
28 ms |
82524 KB |
Output is correct |
29 |
Correct |
22 ms |
81552 KB |
Output is correct |
30 |
Correct |
18 ms |
80476 KB |
Output is correct |
31 |
Correct |
20 ms |
80476 KB |
Output is correct |
32 |
Correct |
19 ms |
80476 KB |
Output is correct |
33 |
Correct |
18 ms |
80476 KB |
Output is correct |
34 |
Correct |
22 ms |
81708 KB |
Output is correct |
35 |
Correct |
18 ms |
80728 KB |
Output is correct |
36 |
Correct |
17 ms |
80476 KB |
Output is correct |
37 |
Correct |
17 ms |
80476 KB |
Output is correct |
38 |
Correct |
17 ms |
80476 KB |
Output is correct |
39 |
Correct |
18 ms |
80476 KB |
Output is correct |
40 |
Correct |
686 ms |
102856 KB |
Output is correct |
41 |
Correct |
541 ms |
103384 KB |
Output is correct |
42 |
Correct |
584 ms |
103252 KB |
Output is correct |
43 |
Correct |
353 ms |
98748 KB |
Output is correct |
44 |
Correct |
378 ms |
98764 KB |
Output is correct |
45 |
Correct |
531 ms |
102992 KB |
Output is correct |
46 |
Correct |
565 ms |
102712 KB |
Output is correct |
47 |
Correct |
515 ms |
102704 KB |
Output is correct |
48 |
Correct |
414 ms |
98160 KB |
Output is correct |
49 |
Correct |
383 ms |
102600 KB |
Output is correct |
50 |
Correct |
531 ms |
102604 KB |
Output is correct |
51 |
Correct |
491 ms |
102916 KB |
Output is correct |