Submission #744440

#	Time	Username	Problem	Language	Result	Execution time	Memory
744440		MODDI	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	403 ms	21280 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m, s1, e1, s2, e2;
const ll inf = 1e18;
vector<pii> G[100100];
vl dijkstra(int start){
	vl dist(n);
	for(int i = 0; i < n; i++)	dist[i] = inf;
	priority_queue<pll, vector<pll>, greater<pll>>q;
	q.push({0, start});
	dist[start] = 0;
	while(!q.empty()){
		pll x = q.top();
		q.pop();
		if(dist[x.second] < x.first)	continue;
		for(pii y : G[x.second]){
			if(x.first + y.second < dist[y.first]){
				dist[y.first] = x.first + y.second;
				q.push({dist[y.first], y.first});
			}
		}
	}
	return dist;
}
ll pair1[2][100100], pair2[2][100100];
pair<ll,ll> st[100100];
bool ok[100100];
pll comb(pll a, pll b) {
    return {min(a.first,b.first),min(a.second,b.second)};
}
int main(){
	cin>>n>>m>>s1>>e1>>s2>>e2;
	s1--;
	e1--;
	s2--;
	e2--;
	for(int i = 0; i < m; i++){
		ll a, b, c;
		cin>>a>>b>>c;
		a--; b--;
		G[a].pb(mp(b,c));
		G[b].pb(mp(a,c));
	}
//	assert(false);
	vl arr = dijkstra(s1);
	for(int i = 0; i < n; i++)	pair1[0][i]	= arr[i];
	arr = dijkstra(e1);
	for(int i = 0; i < n; i++)	pair1[1][i] = arr[i];
	arr = dijkstra(s2);
	for(int i = 0; i < n; i++)	pair2[0][i] = arr[i];
	arr = dijkstra(e2);
	for(int i = 0; i < n; i++)	pair2[1][i] = arr[i];
//	assert(false);
	for(int i = 0; i < n; i++)	st[i] = {inf, inf};
	ll ans = pair2[0][e2];
	vector<pll> v;
	memset(ok, false, sizeof ok);
	for(int i = 0; i < n; i++){
		if (pair1[0][i]+pair1[1][i] == pair1[0][e1]) {
        ok[i] = 1;
        v.pb({pair1[0][i],i});
    	}
    }
    sort(v.rbegin(),v.rend());
    for (auto a: v) {
        for (auto t: G[a.second]) if (ok[t.first]) st[a.second] = comb(st[a.second],st[t.first]);
        ans = min(ans,min(st[a.second].first+pair2[1][a.second],st[a.second].second+pair2[0][a.second]));
        st[a.second] = comb(st[a.second],{pair2[0][a.second],pair2[1][a.second]});
    }
	cout<<ans<<endl;
	return 0;
}

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