Submission #834268

#	Time	Username	Problem	Language	Result	Execution time	Memory
834268		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	2071 ms	31156 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];
set<ll> par[N];
bool vis[N];
ll ans=llINF;

void dfs(ll curr, ll minu, ll minv){
//	if(vis[curr])return;
	if(curr==s){
		ans = min(ans, minu+minv);
	}
	for(auto i:par[curr]) dfs(i, min(minu, du[i]), min(minv, dv[i]));
}

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;

	loop(i,n) vis[i] = false;
	ans = min(ans, du[v]);
	dfs(t, du[t], dv[t]);
	
	cout << ans << endl;
	
	return 0;
}

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