#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (100005)
ll N,M,S,T,U,V;
vector<pair<ll,ll> > v[MAXN];
ll distS[MAXN], distT[MAXN];
void dijkstra(ll start){
ll dist[MAXN];
memset(dist,-1,sizeof(dist));
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
pq.push({0,start});
dist[start] = 0;
while(!pq.empty()){
ll d = pq.top().first;
ll x = pq.top().second;
pq.pop();
if(d != dist[x]){
continue;
}
for(auto u : v[x]){
if(dist[u.first] == -1 || dist[u.first] > dist[x] + u.second){
dist[u.first] = dist[x] + u.second;
pq.push({dist[u.first],u.first});
}
}
}
if(start == S){
for(ll i = 0;i < N;i++){
distS[i] = dist[i];
}
}else if(start == T){
for(ll i = 0;i < N;i++){
distT[i] = dist[i];
}
}else{
assert(false);
}
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
cin>>N>>M>>S>>T>>U>>V;
S--, T--, U--, V--;
for(ll i = 0;i < M;i++){
ll a,b,c;
cin>>a>>b>>c;
a--, b--;
v[a].push_back({b,c});
v[b].push_back({a,c});
}
memset(distS,-1,sizeof(distS));
dijkstra(S);
memset(distT,-1,sizeof(distT));
dijkstra(T);
priority_queue<pair<pair<ll,pair<ll,ll> >,pair<ll,ll> >,vector<pair<pair<ll,pair<ll,ll> >,pair<ll,ll> > >,greater<pair<pair<ll,pair<ll,ll> >,pair<ll,ll> > > > pq;
ll dist[N][3]; //not entered free path yet, currently inside free path, already exited free path
memset(dist,-1,sizeof(dist));
dist[U][0] = 0;
pq.push({{0,{-1,0}},{U,0}});
while(!pq.empty()){
ll d = pq.top().first.first;
ll p = pq.top().first.second.first;
ll pw = pq.top().first.second.second;
ll x = pq.top().second.first;
ll type = pq.top().second.second;
pq.pop();
if(d != dist[x][type]){
continue;
}
for(auto u : v[x]){
if(type == 0){
//enter free path
if(min(distS[x] + u.second + distT[u.first],distT[x] + u.second + distS[u.first]) == distS[T]){
if(dist[u.first][1] == -1 || dist[x][0] < dist[u.first][1]){
dist[u.first][1] = dist[x][0];
pq.push({{dist[u.first][1],{x,u.second}},{u.first,1}});
}
}
//don't enter free path yet
if(dist[u.first][0] == -1 || dist[x][0] + u.second < dist[u.first][0]){
dist[u.first][0] = dist[x][0] + u.second;
pq.push({{dist[u.first][0],{x,u.second}},{u.first,0}});
}
}else if(type == 1){
//continue free path
if(min(distS[p] + pw + u.second + distT[u.first],distT[p] + pw + u.second + distS[u.first]) == distS[T] && min(distS[x] + u.second + distT[u.first],distT[x] + u.second + distS[u.first]) == distS[T]){
if(dist[u.first][1] == -1 || dist[x][1] < dist[u.first][1]){
dist[u.first][1] = dist[x][1];
pq.push({{dist[u.first][1],{x,u.second}},{u.first,1}});
}
}
//leave free path
if(dist[u.first][2] == -1 || dist[x][1] + u.second < dist[u.first][2]){
dist[u.first][2] = dist[x][1] + u.second;
pq.push({{dist[u.first][2],{x,u.second}},{u.first,2}});
}
}else if(type == 2){
if(dist[u.first][2] == -1 || dist[x][2] + u.second < dist[u.first][2]){
dist[u.first][2] = dist[x][2] + u.second;
pq.push({{dist[u.first][2],{x,u.second}},{u.first,2}});
}
}
}
}
ll ans = 1e18;
if(dist[V][0] != -1) ans = min(ans,dist[V][0]);
if(dist[V][1] != -1) ans = min(ans,dist[V][1]);
if(dist[V][2] != -1) ans = min(ans,dist[V][2]);
cout<<ans<<'\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
243 ms |
35044 KB |
Output is correct |
2 |
Correct |
258 ms |
27164 KB |
Output is correct |
3 |
Correct |
287 ms |
35244 KB |
Output is correct |
4 |
Correct |
215 ms |
27780 KB |
Output is correct |
5 |
Correct |
329 ms |
33884 KB |
Output is correct |
6 |
Correct |
258 ms |
34496 KB |
Output is correct |
7 |
Correct |
276 ms |
33476 KB |
Output is correct |
8 |
Correct |
324 ms |
33288 KB |
Output is correct |
9 |
Correct |
229 ms |
27968 KB |
Output is correct |
10 |
Correct |
214 ms |
29636 KB |
Output is correct |
11 |
Correct |
86 ms |
16592 KB |
Output is correct |
12 |
Correct |
254 ms |
28152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
293 ms |
27460 KB |
Output is correct |
2 |
Correct |
288 ms |
28364 KB |
Output is correct |
3 |
Correct |
282 ms |
32692 KB |
Output is correct |
4 |
Correct |
263 ms |
28852 KB |
Output is correct |
5 |
Correct |
302 ms |
28308 KB |
Output is correct |
6 |
Correct |
261 ms |
32756 KB |
Output is correct |
7 |
Correct |
317 ms |
32524 KB |
Output is correct |
8 |
Correct |
293 ms |
28360 KB |
Output is correct |
9 |
Correct |
288 ms |
28648 KB |
Output is correct |
10 |
Correct |
301 ms |
28144 KB |
Output is correct |
11 |
Correct |
101 ms |
19724 KB |
Output is correct |
12 |
Correct |
288 ms |
33208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
7004 KB |
Output is correct |
2 |
Correct |
3 ms |
4956 KB |
Output is correct |
3 |
Correct |
2 ms |
5212 KB |
Output is correct |
4 |
Correct |
12 ms |
8540 KB |
Output is correct |
5 |
Correct |
8 ms |
6924 KB |
Output is correct |
6 |
Correct |
2 ms |
5208 KB |
Output is correct |
7 |
Correct |
3 ms |
5212 KB |
Output is correct |
8 |
Correct |
4 ms |
5228 KB |
Output is correct |
9 |
Correct |
3 ms |
5212 KB |
Output is correct |
10 |
Correct |
7 ms |
6744 KB |
Output is correct |
11 |
Correct |
2 ms |
4956 KB |
Output is correct |
12 |
Correct |
2 ms |
4956 KB |
Output is correct |
13 |
Correct |
2 ms |
5208 KB |
Output is correct |
14 |
Correct |
3 ms |
5212 KB |
Output is correct |
15 |
Correct |
3 ms |
5212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
243 ms |
35044 KB |
Output is correct |
2 |
Correct |
258 ms |
27164 KB |
Output is correct |
3 |
Correct |
287 ms |
35244 KB |
Output is correct |
4 |
Correct |
215 ms |
27780 KB |
Output is correct |
5 |
Correct |
329 ms |
33884 KB |
Output is correct |
6 |
Correct |
258 ms |
34496 KB |
Output is correct |
7 |
Correct |
276 ms |
33476 KB |
Output is correct |
8 |
Correct |
324 ms |
33288 KB |
Output is correct |
9 |
Correct |
229 ms |
27968 KB |
Output is correct |
10 |
Correct |
214 ms |
29636 KB |
Output is correct |
11 |
Correct |
86 ms |
16592 KB |
Output is correct |
12 |
Correct |
254 ms |
28152 KB |
Output is correct |
13 |
Correct |
293 ms |
27460 KB |
Output is correct |
14 |
Correct |
288 ms |
28364 KB |
Output is correct |
15 |
Correct |
282 ms |
32692 KB |
Output is correct |
16 |
Correct |
263 ms |
28852 KB |
Output is correct |
17 |
Correct |
302 ms |
28308 KB |
Output is correct |
18 |
Correct |
261 ms |
32756 KB |
Output is correct |
19 |
Correct |
317 ms |
32524 KB |
Output is correct |
20 |
Correct |
293 ms |
28360 KB |
Output is correct |
21 |
Correct |
288 ms |
28648 KB |
Output is correct |
22 |
Correct |
301 ms |
28144 KB |
Output is correct |
23 |
Correct |
101 ms |
19724 KB |
Output is correct |
24 |
Correct |
288 ms |
33208 KB |
Output is correct |
25 |
Correct |
8 ms |
7004 KB |
Output is correct |
26 |
Correct |
3 ms |
4956 KB |
Output is correct |
27 |
Correct |
2 ms |
5212 KB |
Output is correct |
28 |
Correct |
12 ms |
8540 KB |
Output is correct |
29 |
Correct |
8 ms |
6924 KB |
Output is correct |
30 |
Correct |
2 ms |
5208 KB |
Output is correct |
31 |
Correct |
3 ms |
5212 KB |
Output is correct |
32 |
Correct |
4 ms |
5228 KB |
Output is correct |
33 |
Correct |
3 ms |
5212 KB |
Output is correct |
34 |
Correct |
7 ms |
6744 KB |
Output is correct |
35 |
Correct |
2 ms |
4956 KB |
Output is correct |
36 |
Correct |
2 ms |
4956 KB |
Output is correct |
37 |
Correct |
2 ms |
5208 KB |
Output is correct |
38 |
Correct |
3 ms |
5212 KB |
Output is correct |
39 |
Correct |
3 ms |
5212 KB |
Output is correct |
40 |
Correct |
234 ms |
34012 KB |
Output is correct |
41 |
Correct |
236 ms |
25200 KB |
Output is correct |
42 |
Correct |
218 ms |
25196 KB |
Output is correct |
43 |
Correct |
125 ms |
19952 KB |
Output is correct |
44 |
Correct |
128 ms |
21104 KB |
Output is correct |
45 |
Correct |
289 ms |
32400 KB |
Output is correct |
46 |
Correct |
273 ms |
32860 KB |
Output is correct |
47 |
Correct |
226 ms |
30196 KB |
Output is correct |
48 |
Correct |
120 ms |
19908 KB |
Output is correct |
49 |
Correct |
191 ms |
34172 KB |
Output is correct |
50 |
Correct |
259 ms |
33824 KB |
Output is correct |
51 |
Correct |
309 ms |
33500 KB |
Output is correct |