Submission #678637

#	Time	Username	Problem	Language	Result	Execution time	Memory
678637		anhduc2701	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	119 ms	24420 KiB

commuter_pass

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI 3.14159265359
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x) (1LL<<(x))
#define task "tnc"  
using namespace std;
typedef long long ll;
const ll INF=1e18;
const int maxn=1e5+5;
const int mod=1e9+7;
const int mo=998244353;
using pi=pair<ll,ll>;
using vi=vector<ll>;
using pii=pair<pair<ll,ll>,ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,m;
struct Edge{
	int u,v,w,id;
	Edge(){}
	Edge(int _u,int _v,int _w,int _id){
		u=_u;
		v=_v;
		w=_w;
		id=_id;
	}
}ed[maxn];
vector<Edge>G[maxn];
vector<pair<int,int>>trace[maxn];
vector<int>G2[maxn];
int d[maxn];
int deg[maxn];
int du[maxn];
int dv[maxn];
int dp[maxn];
int dp1[maxn];
int ok[maxn];
int s,t;
int u,v;
void DIJ(){
	for(int i=1;i<=n;i++)d[i]=INF;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	pq.push({0,s});
	d[s]=0;
	while(pq.size()){
		pair<int,int>cha=pq.top();
		pq.pop();
		if(d[cha.se]!=cha.fi)continue;
		for(Edge canh:G[cha.se]){
			if(d[cha.second]+canh.w<d[canh.v]){
				d[canh.v]=d[cha.second]+canh.w;
				trace[canh.v].clear();
				trace[canh.v].pb({cha.se,canh.id});
				pq.push({d[canh.v],canh.v});
			}
			else if(d[cha.se]+canh.w==d[canh.v]){
				trace[canh.v].pb({cha.se,canh.id});
			}
		}
	}
}
void DIJ1(){
	for(int i=1;i<=n;i++)du[i]=INF;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	pq.push({0,u});
	du[u]=0;
	while(pq.size()){
		pair<int,int>cha=pq.top();
		pq.pop();
		if(du[cha.se]!=cha.fi)continue;
		for(Edge canh:G[cha.se]){
			if(du[cha.second]+canh.w<du[canh.v]){
				du[canh.v]=du[cha.second]+canh.w;
				pq.push({du[canh.v],canh.v});
			}
		}
	}
}
void DIJ2(){
	for(int i=1;i<=n;i++)dv[i]=INF;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	pq.push({0,v});
	dv[v]=0;
	while(pq.size()){
		pair<int,int>cha=pq.top();
		pq.pop();
		if(dv[cha.se]!=cha.fi)continue;
		for(Edge canh:G[cha.se]){

			if(dv[cha.second]+canh.w<dv[canh.v]){
				dv[canh.v]=dv[cha.second]+canh.w;
				pq.push({dv[canh.v],canh.v});
			}
		}
	}
}
void get(int dinh){
	deg[dinh]=trace[dinh].size();
	ok[dinh]=1;
	for(auto v1:trace[dinh]){
		G2[v1.first].pb(dinh);
		if(ok[v1.first]==0){

			get(v1.first);
		}
	}
}
signed main()
{
	cin.tie(0),cout.tie(0)->sync_with_stdio(0);
    //freopen(task".inp" , "r" , stdin);
    //freopen(task".out" , "w" , stdout);
    cin>>n>>m>>s>>t>>u>>v;
    for(int i=1;i<=m;i++){
    	int x,y,w;
    	cin>>x>>y>>w;
    	G[x].pb(Edge(x,y,w,i));
    	G[y].pb(Edge(y,x,w,i));
    	ed[i]=Edge(x,y,w,i);
    }
    DIJ();
    DIJ1();
    DIJ2();
    int ans=du[v];
    get(t);
    dp[s]=du[s];
    queue<int>qu;
    qu.push(s);
    vector<int>topo;
    while(qu.size()){
    	int dinh=qu.front();
    	qu.pop();
    	topo.pb(dinh);
    	for(auto canh:G2[dinh]){
    		deg[canh]--;
    		if(deg[canh]==0){
    			qu.push(canh);
    		}
    	}
    }
    for(auto dinh:topo){
    	dp[dinh]=du[dinh];
    }
    for(auto dinh:topo){
    	for(auto den:trace[dinh]){

    		dp[dinh]=min(dp[den.fi],dp[dinh]);
    	}
    	ans=min(ans,dp[dinh]+dv[dinh]);
    }
    reverse(topo.begin(),topo.end());
    
    for(auto dinh:topo){
    	dp1[dinh]=dv[dinh];
    }
    for(auto dinh:topo){
    	for(auto den:G2[dinh]){
    		dp1[dinh]=min(dp1[den],dp1[dinh]);
    	}
    	ans=min(ans,dp1[dinh]+du[dinh]);
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45