제출 #638767

#제출 시각아이디문제언어결과실행 시간메모리
638767victor_gaoCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
515 ms65980 KiB
//#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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...