Submission #836770

#	Time	Username	Problem	Language	Result	Execution time	Memory
836770		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	375 ms	34692 KiB

commuter_pass

#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define INF INT_MAX
#define ENF INT_MIN
#define llINF 1e17
#define loop(i,n) for(int i=1 ; i<=n ; i++)
#define loop0(i,n) for(int i=0 ; i<n ; i++)
#define debug(arr, n) for(int i=1 ; i<=n ; i++) cout << i << ": " << arr[i] << endl;
#define debug0(arr, n) for(int i=0 ; i<n ; i++) cout << i << ": " << arr[i] << endl;
#define mem(a,b) memset(a, b, sizeof(a))
#define pllll pair<ll,ll>
#define OUT(x) if(x) cout << "YES\n"; else cout << "NO\n";

using namespace std;
const int N = 1e5 + 5;

ll n,m,s,t,u,v;
vector<pllll> adj[N];
ll dist[N], du[N], dv[N], d[N];
set<ll> par[N];
bool vis[N];
ll ans=llINF;
pllll dp[N];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m >> s >> t >> u >> v;
	loop(i,m){
		ll t1, t2, t3;
		cin >> t1 >> t2 >> t3;
		adj[t1].pb({t2,t3});
		adj[t2].pb({t1,t3});
	}
	
	//cari shortestpath dari u ke v
	loop(i,n)dist[i] = llINF;
	dist[s] = 0;
	priority_queue<pllll, vector<pllll>, greater<pllll>> pq;
	pq.push({0,s});
	while(!pq.empty()){
		ll currdist, currnode;
		currdist = pq.top().first;
		currnode = pq.top().second;
		pq.pop();
		if(currdist != dist[currnode]) continue;
		for(auto edge: adj[currnode]){
			ll to = edge.first;
			ll c = edge.second;
			
			if(currdist + c == dist[to]){
				par[to].insert(currnode);
			}
			else if(currdist + c < dist[to]){
				par[to].clear();
				par[to].insert(currnode);
				dist[to] = dist[currnode]+c;
				pq.push({dist[to], to});
			}
		}
	}

	//djikstra dari u
	loop(i,n)du[i] = llINF;
	du[u] = 0;
//	priority_queue<pllll, vector<pllll>, greater<pllll>> pq;
	pq.push({0,u});
	while(!pq.empty()){
		ll currdist, currnode;
		currdist = pq.top().first;
		currnode = pq.top().second;
		pq.pop();
		if(currdist != du[currnode]) continue;
		for(auto edge: adj[currnode]){
			ll to = edge.first;
			ll c = edge.second;
			
			if(currdist + c < du[to]){
				du[to] = du[currnode]+c;
				pq.push({du[to], to});
			}
		}
	}
//	loop(i,n) cout << du[i] << endl;

	//djikstra dari v
	loop(i,n)dv[i] = llINF;
	dv[v] = 0;
//	priority_queue<pllll, vector<pllll>, greater<pllll>> pq;
	pq.push({0,v});
	while(!pq.empty()){
		ll currdist, currnode;
		currdist = pq.top().first;
		currnode = pq.top().second;
		pq.pop();
		if(currdist != dv[currnode]) continue;
		for(auto edge: adj[currnode]){
			ll to = edge.first;
			ll c = edge.second;
			
			if(currdist + c < dv[to]){
				dv[to] = dv[currnode]+c;
				pq.push({dv[to], to});
			}
		}
	}
//	loop(i,n) cout << dv[i] << endl;

	ans = min(ans, du[v]);
	
	loop(i,n)d[i] = llINF;
	d[t] = du[t]+dv[t];
	priority_queue<pair<pllll, pllll>, vector<pair<pllll, pllll>>, greater<pair<pllll, pllll>> > q;
	q.push({{du[t]+dv[t], t}, {du[t], dv[t]}});
	while(!q.empty()){
		ll currdist, currnode, a, b;
		currdist = q.top().first.first;
		currnode = q.top().first.second;
		a = q.top().second.first;
		b = q.top().second.second;
		
		q.pop();
		
		if(currdist != d[currnode]) continue;
		for(auto i:par[currnode]){
			ll to = i;
			ll x = min(a, du[i]);
			ll y = min(b, dv[i]);
			if(x+y < d[to]){
				d[to] = x+y;
				q.push({{x+y, to},{x, y}});
			}
		}
	}
	
	ans = min(ans, d[s]);
	cout << ans << endl;
	
	return 0;
}

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