//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,m,s,t,u,v,dis[N][3][2],path[N],can[N];
// 0 非路上 1 順 2 逆
vector<pii>g[N];
vector<pair<pii,int> >edge,ng[N];
void dijkstra1(){
priority_queue<pii,vector<pii>,greater<pii> >pq;
for (int i=1;i<=n;i++)
path[i]=1e18;
path[s]=0;
pq.push({path[s],s});
while (!pq.empty()){
pii np=pq.top(); pq.pop();
if (np.x!=path[np.y]) continue;
for (auto i:g[np.y]){
if (path[i.x]>np.x+i.y){
path[i.x]=np.x+i.y;
pq.push({path[i.x],i.x});
}
}
}
queue<int>q;
can[t]=1;
q.push(t);
while (!q.empty()){
int np=q.front(); q.pop();
for (auto i:g[np]){
if (!can[i.x]&&path[i.x]+i.y==path[np]){
can[i.x]=1;
q.push(i.x);
}
}
}
}
void build(){
for (auto i:edge){
if (can[i.x.x]&&can[i.x.y]){
if (path[i.x.x]+i.y==path[i.x.y]){
ng[i.x.x].push_back({{i.x.y,0},1});
ng[i.x.y].push_back({{i.x.x,0},2});
}
else if (path[i.x.y]+i.y==path[i.x.x]){
ng[i.x.y].push_back({{i.x.x,0},1});
ng[i.x.x].push_back({{i.x.y,0},2});
}
}
ng[i.x.x].push_back({{i.x.y,i.y},0});
ng[i.x.y].push_back({{i.x.x,i.y},0});
}
}
struct Node{
int d,p,go,k;
Node(int a,int b,int c,int d):d(a),p(b),go(c),k(d){}
bool operator<(const Node a)const{ return d>a.d; }
};
priority_queue<Node>pq;
void relax(Node now,pair<pii,int>e){
Node ok=Node(0,0,0,0);
if (e.y==0){
if (now.d+e.x.y<dis[e.x.x][now.go][0]){
dis[e.x.x][now.go][0]=now.d+e.x.y;
ok=Node(now.d+e.x.y,e.x.x,now.go,0);
}
else return;
}
else {
if (now.go==e.y){
if (!now.k) return;
else if (now.d+e.x.y<dis[e.x.x][now.go][1]){
dis[e.x.x][now.go][1]=now.d+e.x.y;
ok=Node(now.d+e.x.y,e.x.x,now.go,1);
}
else return;
}
else {
if (now.go==0){
if (now.d+e.x.y<dis[e.x.x][e.y][1]){
dis[e.x.x][e.y][1]=now.d+e.x.y;
ok=Node(now.d+e.x.y,e.x.x,e.y,1);
}
else return;
}
else return;
}
}
pq.push(ok);
}
void dijkstra2(){
for (int i=1;i<=n;i++){
for (int j=0;j<3;j++){
for (int k=0;k<2;k++)
dis[i][j][k]=1e18;
}
}
dis[u][0][0]=0;
pq.push(Node(0,u,0,0));
while (!pq.empty()){
Node np=pq.top(); pq.pop();
// cout<<np.p<<" "<<np.go<<" "<<np.k<<" "<<np.d<<'\n';
if (np.d!=dis[np.p][np.go][np.k]) continue;
for (auto i:ng[np.p])
relax(np,i);
}
}
signed main(){
fast
cin>>n>>m>>s>>t>>u>>v;
for (int i=1;i<=m;i++){
int a,b,c; cin>>a>>b>>c;
edge.push_back({{a,b},c});
g[a].push_back({b,c});
g[b].push_back({a,c});
}
dijkstra1();
build();
dijkstra2();
cout<<min({dis[v][0][0],dis[v][0][1],dis[v][1][0],dis[v][1][1],dis[v][2][0],dis[v][2][1]})<<'\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
351 ms |
52116 KB |
Output is correct |
2 |
Correct |
419 ms |
55480 KB |
Output is correct |
3 |
Correct |
435 ms |
57916 KB |
Output is correct |
4 |
Correct |
336 ms |
52052 KB |
Output is correct |
5 |
Correct |
428 ms |
57872 KB |
Output is correct |
6 |
Correct |
356 ms |
51952 KB |
Output is correct |
7 |
Correct |
439 ms |
58296 KB |
Output is correct |
8 |
Correct |
447 ms |
57592 KB |
Output is correct |
9 |
Correct |
403 ms |
47260 KB |
Output is correct |
10 |
Correct |
314 ms |
47456 KB |
Output is correct |
11 |
Correct |
174 ms |
31272 KB |
Output is correct |
12 |
Correct |
470 ms |
52460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
431 ms |
54844 KB |
Output is correct |
2 |
Correct |
429 ms |
55280 KB |
Output is correct |
3 |
Correct |
433 ms |
54844 KB |
Output is correct |
4 |
Correct |
437 ms |
55144 KB |
Output is correct |
5 |
Correct |
433 ms |
55652 KB |
Output is correct |
6 |
Correct |
439 ms |
57580 KB |
Output is correct |
7 |
Correct |
478 ms |
58080 KB |
Output is correct |
8 |
Correct |
429 ms |
55364 KB |
Output is correct |
9 |
Correct |
449 ms |
55776 KB |
Output is correct |
10 |
Correct |
432 ms |
55044 KB |
Output is correct |
11 |
Correct |
201 ms |
34676 KB |
Output is correct |
12 |
Correct |
434 ms |
57884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
9396 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
20 ms |
12552 KB |
Output is correct |
5 |
Correct |
12 ms |
8972 KB |
Output is correct |
6 |
Correct |
3 ms |
5332 KB |
Output is correct |
7 |
Correct |
5 ms |
5460 KB |
Output is correct |
8 |
Correct |
4 ms |
5588 KB |
Output is correct |
9 |
Correct |
3 ms |
5332 KB |
Output is correct |
10 |
Correct |
12 ms |
8928 KB |
Output is correct |
11 |
Correct |
3 ms |
5076 KB |
Output is correct |
12 |
Correct |
3 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5172 KB |
Output is correct |
14 |
Correct |
3 ms |
5204 KB |
Output is correct |
15 |
Correct |
3 ms |
5204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
351 ms |
52116 KB |
Output is correct |
2 |
Correct |
419 ms |
55480 KB |
Output is correct |
3 |
Correct |
435 ms |
57916 KB |
Output is correct |
4 |
Correct |
336 ms |
52052 KB |
Output is correct |
5 |
Correct |
428 ms |
57872 KB |
Output is correct |
6 |
Correct |
356 ms |
51952 KB |
Output is correct |
7 |
Correct |
439 ms |
58296 KB |
Output is correct |
8 |
Correct |
447 ms |
57592 KB |
Output is correct |
9 |
Correct |
403 ms |
47260 KB |
Output is correct |
10 |
Correct |
314 ms |
47456 KB |
Output is correct |
11 |
Correct |
174 ms |
31272 KB |
Output is correct |
12 |
Correct |
470 ms |
52460 KB |
Output is correct |
13 |
Correct |
431 ms |
54844 KB |
Output is correct |
14 |
Correct |
429 ms |
55280 KB |
Output is correct |
15 |
Correct |
433 ms |
54844 KB |
Output is correct |
16 |
Correct |
437 ms |
55144 KB |
Output is correct |
17 |
Correct |
433 ms |
55652 KB |
Output is correct |
18 |
Correct |
439 ms |
57580 KB |
Output is correct |
19 |
Correct |
478 ms |
58080 KB |
Output is correct |
20 |
Correct |
429 ms |
55364 KB |
Output is correct |
21 |
Correct |
449 ms |
55776 KB |
Output is correct |
22 |
Correct |
432 ms |
55044 KB |
Output is correct |
23 |
Correct |
201 ms |
34676 KB |
Output is correct |
24 |
Correct |
434 ms |
57884 KB |
Output is correct |
25 |
Correct |
14 ms |
9396 KB |
Output is correct |
26 |
Correct |
3 ms |
5076 KB |
Output is correct |
27 |
Correct |
3 ms |
5076 KB |
Output is correct |
28 |
Correct |
20 ms |
12552 KB |
Output is correct |
29 |
Correct |
12 ms |
8972 KB |
Output is correct |
30 |
Correct |
3 ms |
5332 KB |
Output is correct |
31 |
Correct |
5 ms |
5460 KB |
Output is correct |
32 |
Correct |
4 ms |
5588 KB |
Output is correct |
33 |
Correct |
3 ms |
5332 KB |
Output is correct |
34 |
Correct |
12 ms |
8928 KB |
Output is correct |
35 |
Correct |
3 ms |
5076 KB |
Output is correct |
36 |
Correct |
3 ms |
5076 KB |
Output is correct |
37 |
Correct |
3 ms |
5172 KB |
Output is correct |
38 |
Correct |
3 ms |
5204 KB |
Output is correct |
39 |
Correct |
3 ms |
5204 KB |
Output is correct |
40 |
Correct |
388 ms |
57848 KB |
Output is correct |
41 |
Correct |
393 ms |
47200 KB |
Output is correct |
42 |
Correct |
384 ms |
47340 KB |
Output is correct |
43 |
Correct |
256 ms |
36608 KB |
Output is correct |
44 |
Correct |
266 ms |
36708 KB |
Output is correct |
45 |
Correct |
515 ms |
65924 KB |
Output is correct |
46 |
Correct |
512 ms |
65976 KB |
Output is correct |
47 |
Correct |
351 ms |
52256 KB |
Output is correct |
48 |
Correct |
265 ms |
36708 KB |
Output is correct |
49 |
Correct |
340 ms |
57972 KB |
Output is correct |
50 |
Correct |
495 ms |
63672 KB |
Output is correct |
51 |
Correct |
506 ms |
65980 KB |
Output is correct |