#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define maxn 100001
#define INF (ll)1e16
#define int ll
typedef pair <pi,ll> pii;
int N,M,S,T,U,V;
int distS[maxn],distV[maxn], distU[maxn],distT[maxn];
vpi adj[maxn];
vi dag[maxn];
int dp[maxn];
int minE[maxn];
int minS[maxn];
int dpf(int x){
if (dp[x] != -1) return dp[x];
dp[x] = INF;
int E = INF;
int mnS = INF;
aFOR(i,dag[x]){
if (minE[x] != -1) E = min(E,minE[x]);
if (minS[x] != -1) mnS = min(mnS,minS[x]);
dp[x] = min(dp[x],dpf(i));
}
if (E != -1 && distU[x] != -1) dp[x] = min(dp[x],distU[x] + E);
if (distV[x] != -1 && mnS != -1) dp[x] = min(dp[x],distV[x] + mnS);
if (distU[x] != -1 && distV[x] != -1) dp[x] = min(dp[x],distU[x] + distV[x]);
return dp[x];
}
bool vis[maxn];
void dfs(int x){ //to find minE
if (vis[x]) return;
vis[x] = 1;
minE[x] = distV[x];
minS[x] = distU[x];
aFOR(i,dag[x]){
dfs(i);
if (minE[i] != -1) minE[x] = min(minE[x],minE[i]);
if (minS[i] != -1) minS[x] = min(minS[x],minS[i]);
}
}
bool cycle = 0;
int vis2[maxn];
void cycle_find(int x){
if (vis2[x] == 2) return;
if (vis2[x] == 1){
cycle = 1;
return;
}
if (cycle) return;
vis2[x] = 1;
aFOR(i,dag[x]){
cycle_find(i);
}
vis2[x] = 2;
}
int32_t main(){
fast;
cin>>N>>M>>S>>T>>U>>V;
vector <pii> edges;
FOR(i,0,M-1){
int a,b,c; cin>>a>>b>>c;
adj[a].pb(pi(b,c)); adj[b].pb(pi(a,c));
edges.pb(pii(pi(a,b),c));
}
int rt = S;
priority_queue <pi,vector <pi>, greater <pi> > pq;
mem(distS,-1);
distS[rt] = 0;
pq.push(pi(0,rt));
while (!pq.empty()){
pi cur = pq.top(); pq.pop();
if (distS[cur.s] != cur.f) continue;
aFOR(i,adj[cur.s]){
if (distS[i.f] == -1 || distS[i.f] > cur.f + i.s){
distS[i.f] = cur.f + i.s;
pq.push(pi(distS[i.f],i.f));
}
}
}
rt = T;
mem(distT,-1);
distT[rt] = 0;
pq.push(pi(0,rt));
while (!pq.empty()){
pi cur = pq.top(); pq.pop();
if (distT[cur.s] != cur.f) continue;
aFOR(i,adj[cur.s]){
if (distT[i.f] == -1 || distT[i.f] > cur.f + i.s){
distT[i.f] = cur.f + i.s;
pq.push(pi(distT[i.f],i.f));
}
}
}
rt = U;
mem(distU,-1);
distU[rt] = 0;
pq.push(pi(0,rt));
while (!pq.empty()){
pi cur = pq.top(); pq.pop();
if (distU[cur.s] != cur.f) continue;
aFOR(i,adj[cur.s]){
if (distU[i.f] == -1 || distU[i.f] > cur.f + i.s){
distU[i.f] = cur.f + i.s;
pq.push(pi(distU[i.f],i.f));
}
}
}
rt = V;
mem(distV,-1);
distV[rt] = 0;
pq.push(pi(0,rt));
while (!pq.empty()){
pi cur = pq.top(); pq.pop();
if (distV[cur.s] != cur.f) continue;
aFOR(i,adj[cur.s]){
if (distV[i.f] == -1 || distV[i.f] > cur.f + i.s){
distV[i.f] = cur.f + i.s;
pq.push(pi(distV[i.f],i.f));
}
}
}
aFOR(i,edges){
int a = i.f.f, b = i.f.s, c = i.s;
if (!(distS[a] == -1 || distT[b] == -1) && distS[a] + c + distT[b] == distS[T]){
dag[a].pb(b);
//cout<<a<<' '<<b<<'\n';
}else if(!(distS[b] == -1 || distT[a] == -1) && distS[b] + c + distT[a] == distS[T]){
dag[b].pb(a);
//cout<<b<<' '<<a<<'\n';
}
}
//cycle_find(S);
//if (cycle) assert(0);
dfs(S);
mem(dp,-1);
int ans = dpf(S);
if (distU[V] != -1) ans = min(ans,distU[V]);
cout<<ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
344 ms |
27376 KB |
Output is correct |
2 |
Correct |
366 ms |
27760 KB |
Output is correct |
3 |
Correct |
418 ms |
31960 KB |
Output is correct |
4 |
Correct |
336 ms |
27396 KB |
Output is correct |
5 |
Correct |
347 ms |
27548 KB |
Output is correct |
6 |
Correct |
359 ms |
27684 KB |
Output is correct |
7 |
Correct |
381 ms |
28032 KB |
Output is correct |
8 |
Correct |
366 ms |
27932 KB |
Output is correct |
9 |
Correct |
342 ms |
26008 KB |
Output is correct |
10 |
Correct |
289 ms |
25752 KB |
Output is correct |
11 |
Correct |
156 ms |
21152 KB |
Output is correct |
12 |
Correct |
357 ms |
26008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
374 ms |
29208 KB |
Output is correct |
2 |
Correct |
384 ms |
29156 KB |
Output is correct |
3 |
Correct |
386 ms |
28972 KB |
Output is correct |
4 |
Correct |
404 ms |
29080 KB |
Output is correct |
5 |
Correct |
394 ms |
29336 KB |
Output is correct |
6 |
Correct |
366 ms |
30640 KB |
Output is correct |
7 |
Correct |
386 ms |
31384 KB |
Output is correct |
8 |
Correct |
362 ms |
29080 KB |
Output is correct |
9 |
Correct |
376 ms |
29596 KB |
Output is correct |
10 |
Correct |
380 ms |
28952 KB |
Output is correct |
11 |
Correct |
215 ms |
22920 KB |
Output is correct |
12 |
Correct |
394 ms |
30996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
10936 KB |
Output is correct |
2 |
Correct |
9 ms |
9088 KB |
Output is correct |
3 |
Correct |
9 ms |
9088 KB |
Output is correct |
4 |
Correct |
27 ms |
13364 KB |
Output is correct |
5 |
Correct |
18 ms |
11192 KB |
Output is correct |
6 |
Correct |
10 ms |
9216 KB |
Output is correct |
7 |
Correct |
11 ms |
9216 KB |
Output is correct |
8 |
Correct |
12 ms |
9344 KB |
Output is correct |
9 |
Correct |
10 ms |
9088 KB |
Output is correct |
10 |
Correct |
19 ms |
11224 KB |
Output is correct |
11 |
Correct |
9 ms |
9088 KB |
Output is correct |
12 |
Correct |
10 ms |
9088 KB |
Output is correct |
13 |
Correct |
10 ms |
9088 KB |
Output is correct |
14 |
Correct |
10 ms |
9088 KB |
Output is correct |
15 |
Correct |
10 ms |
9088 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
344 ms |
27376 KB |
Output is correct |
2 |
Correct |
366 ms |
27760 KB |
Output is correct |
3 |
Correct |
418 ms |
31960 KB |
Output is correct |
4 |
Correct |
336 ms |
27396 KB |
Output is correct |
5 |
Correct |
347 ms |
27548 KB |
Output is correct |
6 |
Correct |
359 ms |
27684 KB |
Output is correct |
7 |
Correct |
381 ms |
28032 KB |
Output is correct |
8 |
Correct |
366 ms |
27932 KB |
Output is correct |
9 |
Correct |
342 ms |
26008 KB |
Output is correct |
10 |
Correct |
289 ms |
25752 KB |
Output is correct |
11 |
Correct |
156 ms |
21152 KB |
Output is correct |
12 |
Correct |
357 ms |
26008 KB |
Output is correct |
13 |
Correct |
374 ms |
29208 KB |
Output is correct |
14 |
Correct |
384 ms |
29156 KB |
Output is correct |
15 |
Correct |
386 ms |
28972 KB |
Output is correct |
16 |
Correct |
404 ms |
29080 KB |
Output is correct |
17 |
Correct |
394 ms |
29336 KB |
Output is correct |
18 |
Correct |
366 ms |
30640 KB |
Output is correct |
19 |
Correct |
386 ms |
31384 KB |
Output is correct |
20 |
Correct |
362 ms |
29080 KB |
Output is correct |
21 |
Correct |
376 ms |
29596 KB |
Output is correct |
22 |
Correct |
380 ms |
28952 KB |
Output is correct |
23 |
Correct |
215 ms |
22920 KB |
Output is correct |
24 |
Correct |
394 ms |
30996 KB |
Output is correct |
25 |
Correct |
17 ms |
10936 KB |
Output is correct |
26 |
Correct |
9 ms |
9088 KB |
Output is correct |
27 |
Correct |
9 ms |
9088 KB |
Output is correct |
28 |
Correct |
27 ms |
13364 KB |
Output is correct |
29 |
Correct |
18 ms |
11192 KB |
Output is correct |
30 |
Correct |
10 ms |
9216 KB |
Output is correct |
31 |
Correct |
11 ms |
9216 KB |
Output is correct |
32 |
Correct |
12 ms |
9344 KB |
Output is correct |
33 |
Correct |
10 ms |
9088 KB |
Output is correct |
34 |
Correct |
19 ms |
11224 KB |
Output is correct |
35 |
Correct |
9 ms |
9088 KB |
Output is correct |
36 |
Correct |
10 ms |
9088 KB |
Output is correct |
37 |
Correct |
10 ms |
9088 KB |
Output is correct |
38 |
Correct |
10 ms |
9088 KB |
Output is correct |
39 |
Correct |
10 ms |
9088 KB |
Output is correct |
40 |
Correct |
323 ms |
31112 KB |
Output is correct |
41 |
Correct |
364 ms |
30360 KB |
Output is correct |
42 |
Correct |
315 ms |
30360 KB |
Output is correct |
43 |
Correct |
213 ms |
25492 KB |
Output is correct |
44 |
Correct |
181 ms |
25504 KB |
Output is correct |
45 |
Correct |
445 ms |
32752 KB |
Output is correct |
46 |
Correct |
380 ms |
32372 KB |
Output is correct |
47 |
Correct |
331 ms |
31896 KB |
Output is correct |
48 |
Correct |
190 ms |
23332 KB |
Output is correct |
49 |
Correct |
275 ms |
30616 KB |
Output is correct |
50 |
Correct |
351 ms |
32028 KB |
Output is correct |
51 |
Correct |
340 ms |
32536 KB |
Output is correct |