Submission #227838

#	Time	Username	Problem	Language	Result	Execution time	Memory
227838		jiahng	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	445 ms	32752 KiB

commuter_pass

#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;
	
	
	
	
}

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