//
// ~oisín~ C++ Template
//
#include <bits/stdc++.h>
#define MX_N 200005
#define mp make_pair
#define mod7 1000000007
#define modpi 314159
#define PI 3.141592653589793238
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a) a.begin(),a.end()
#define fi first
#define se second
#define ll long long int
#define ull unsigned long long int
int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] = {+0, +0, +1, -1};
int dy4[4] = {+1, -1, +0, +0};
ll gcd(ull a, ull b){
return (a==0)?b:gcd(b%a,a);
}
ll lcm(ull a, ull b){
return a*(b/gcd(a,b));
}
const long long INF = 1e18;
using namespace std;
int N, M, S, T, U, V;
bool vis[MX_N];
bool topovis[MX_N];
vector<int> toposort;
ll dist[MX_N][3];
ll mass[MX_N];
vector<pair<int, int> > adj[MX_N];
vector<int> dag_adj[MX_N];
ll dpU[MX_N], dpV[MX_N];
void topodfs(int at){
topovis[at] = true;
for(int to : dag_adj[at]){
if(!topovis[to]){
topodfs(to);
}
}
toposort.pb(at);
return;
}
int main(){
cin >> N >> M >> S >> T >> U >> V;
--S, --T, --U, --V;
for(int i=0;i<M;++i){
int u, v;
cin >> u >> v >> mass[i];
--u, --v;
adj[u].pb({v, i});
adj[v].pb({u, i});
}
for(int i=0;i<N;++i){
dist[i][0] = dist[i][1] = dist[i][2] = INF;
}
priority_queue<pair<ll, int> > pq;
dist[S][0] = 0ll;
pq.push({0, S});
while(!pq.empty()){
auto [d, at] = pq.top();
pq.pop();
d *= -1ll;
if(d != dist[at][0]){
continue;
}
for(auto& [to, id] : adj[at]){
if(dist[to][0] > dist[at][0] + mass[id]){
dist[to][0] = dist[at][0] + mass[id];
pq.push({-1ll*dist[to][0], to});
}
}
}
dist[U][1] = 0ll;
pq.push({0, U});
while(!pq.empty()){
auto [d, at] = pq.top();
pq.pop();
d *= -1ll;
if(d != dist[at][1]){
continue;
}
for(auto& [to, id] : adj[at]){
if(dist[to][1] > dist[at][1] + mass[id]){
dist[to][1] = dist[at][1] + mass[id];
pq.push({-1ll*dist[to][1], to});
}
}
}
dist[V][2] = 0ll;
pq.push({0, V});
while(!pq.empty()){
auto [d, at] = pq.top();
pq.pop();
d *= -1ll;
if(d != dist[at][2]){
continue;
}
for(auto& [to, id] : adj[at]){
if(dist[to][2] > dist[at][2] + mass[id]){
dist[to][2] = dist[at][2] + mass[id];
pq.push({-1ll*dist[to][2], to});
}
}
}
memset(vis, 0, sizeof(vis));
queue<int> Q;
vis[T] = true;
Q.push(T);
while(!Q.empty()){
int at = Q.front();
Q.pop();
for(auto& [to, id] : adj[at]){
if(dist[to][0] + mass[id] == dist[at][0]){
dag_adj[to].pb(at);
if(!vis[to]){
vis[to] = true;
Q.push(to);
}
}
}
}
memset(topovis, 0, sizeof(topovis));
topodfs(S);
reverse(All(toposort));
ll ans = dist[V][1];
for(int i=0;i<N;++i){
dpU[i] = dist[i][1];
dpV[i] = dist[i][2];
}
for(int at : toposort){
for(int to : dag_adj[at]){
dpU[to] = min(dpU[to], dpU[at]);
dpV[to] = min(dpV[to], dpV[at]);
}
ans = min(ans, dpU[at] + dist[at][2]);
ans = min(ans, dpV[at] + dist[at][1]);
}
cout << ans << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
563 ms |
23080 KB |
Output is correct |
2 |
Correct |
558 ms |
23392 KB |
Output is correct |
3 |
Correct |
626 ms |
27912 KB |
Output is correct |
4 |
Correct |
482 ms |
22960 KB |
Output is correct |
5 |
Correct |
549 ms |
24284 KB |
Output is correct |
6 |
Correct |
488 ms |
23052 KB |
Output is correct |
7 |
Correct |
539 ms |
24672 KB |
Output is correct |
8 |
Correct |
547 ms |
24556 KB |
Output is correct |
9 |
Correct |
495 ms |
22672 KB |
Output is correct |
10 |
Correct |
484 ms |
22600 KB |
Output is correct |
11 |
Correct |
238 ms |
21416 KB |
Output is correct |
12 |
Correct |
525 ms |
22728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
557 ms |
24740 KB |
Output is correct |
2 |
Correct |
548 ms |
24884 KB |
Output is correct |
3 |
Correct |
563 ms |
24456 KB |
Output is correct |
4 |
Correct |
593 ms |
24832 KB |
Output is correct |
5 |
Correct |
514 ms |
25524 KB |
Output is correct |
6 |
Correct |
540 ms |
27372 KB |
Output is correct |
7 |
Correct |
603 ms |
28260 KB |
Output is correct |
8 |
Correct |
515 ms |
25024 KB |
Output is correct |
9 |
Correct |
545 ms |
25620 KB |
Output is correct |
10 |
Correct |
550 ms |
24688 KB |
Output is correct |
11 |
Correct |
251 ms |
23240 KB |
Output is correct |
12 |
Correct |
574 ms |
27728 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
10948 KB |
Output is correct |
2 |
Correct |
8 ms |
10068 KB |
Output is correct |
3 |
Correct |
12 ms |
10104 KB |
Output is correct |
4 |
Correct |
63 ms |
12528 KB |
Output is correct |
5 |
Correct |
38 ms |
11240 KB |
Output is correct |
6 |
Correct |
9 ms |
10188 KB |
Output is correct |
7 |
Correct |
10 ms |
10188 KB |
Output is correct |
8 |
Correct |
11 ms |
10232 KB |
Output is correct |
9 |
Correct |
10 ms |
10188 KB |
Output is correct |
10 |
Correct |
31 ms |
11332 KB |
Output is correct |
11 |
Correct |
10 ms |
10060 KB |
Output is correct |
12 |
Correct |
8 ms |
10040 KB |
Output is correct |
13 |
Correct |
9 ms |
10060 KB |
Output is correct |
14 |
Correct |
9 ms |
10104 KB |
Output is correct |
15 |
Correct |
9 ms |
10108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
563 ms |
23080 KB |
Output is correct |
2 |
Correct |
558 ms |
23392 KB |
Output is correct |
3 |
Correct |
626 ms |
27912 KB |
Output is correct |
4 |
Correct |
482 ms |
22960 KB |
Output is correct |
5 |
Correct |
549 ms |
24284 KB |
Output is correct |
6 |
Correct |
488 ms |
23052 KB |
Output is correct |
7 |
Correct |
539 ms |
24672 KB |
Output is correct |
8 |
Correct |
547 ms |
24556 KB |
Output is correct |
9 |
Correct |
495 ms |
22672 KB |
Output is correct |
10 |
Correct |
484 ms |
22600 KB |
Output is correct |
11 |
Correct |
238 ms |
21416 KB |
Output is correct |
12 |
Correct |
525 ms |
22728 KB |
Output is correct |
13 |
Correct |
557 ms |
24740 KB |
Output is correct |
14 |
Correct |
548 ms |
24884 KB |
Output is correct |
15 |
Correct |
563 ms |
24456 KB |
Output is correct |
16 |
Correct |
593 ms |
24832 KB |
Output is correct |
17 |
Correct |
514 ms |
25524 KB |
Output is correct |
18 |
Correct |
540 ms |
27372 KB |
Output is correct |
19 |
Correct |
603 ms |
28260 KB |
Output is correct |
20 |
Correct |
515 ms |
25024 KB |
Output is correct |
21 |
Correct |
545 ms |
25620 KB |
Output is correct |
22 |
Correct |
550 ms |
24688 KB |
Output is correct |
23 |
Correct |
251 ms |
23240 KB |
Output is correct |
24 |
Correct |
574 ms |
27728 KB |
Output is correct |
25 |
Correct |
31 ms |
10948 KB |
Output is correct |
26 |
Correct |
8 ms |
10068 KB |
Output is correct |
27 |
Correct |
12 ms |
10104 KB |
Output is correct |
28 |
Correct |
63 ms |
12528 KB |
Output is correct |
29 |
Correct |
38 ms |
11240 KB |
Output is correct |
30 |
Correct |
9 ms |
10188 KB |
Output is correct |
31 |
Correct |
10 ms |
10188 KB |
Output is correct |
32 |
Correct |
11 ms |
10232 KB |
Output is correct |
33 |
Correct |
10 ms |
10188 KB |
Output is correct |
34 |
Correct |
31 ms |
11332 KB |
Output is correct |
35 |
Correct |
10 ms |
10060 KB |
Output is correct |
36 |
Correct |
8 ms |
10040 KB |
Output is correct |
37 |
Correct |
9 ms |
10060 KB |
Output is correct |
38 |
Correct |
9 ms |
10104 KB |
Output is correct |
39 |
Correct |
9 ms |
10108 KB |
Output is correct |
40 |
Correct |
508 ms |
27184 KB |
Output is correct |
41 |
Correct |
525 ms |
27092 KB |
Output is correct |
42 |
Correct |
563 ms |
27016 KB |
Output is correct |
43 |
Correct |
272 ms |
25964 KB |
Output is correct |
44 |
Correct |
270 ms |
25924 KB |
Output is correct |
45 |
Correct |
624 ms |
29484 KB |
Output is correct |
46 |
Correct |
720 ms |
29168 KB |
Output is correct |
47 |
Correct |
561 ms |
26668 KB |
Output is correct |
48 |
Correct |
262 ms |
23856 KB |
Output is correct |
49 |
Correct |
420 ms |
26956 KB |
Output is correct |
50 |
Correct |
592 ms |
28712 KB |
Output is correct |
51 |
Correct |
637 ms |
29340 KB |
Output is correct |