제출 #744427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744427		MODDI	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	423 ms	15916 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<pair<ll, int>> pq;
	pq.push(mp(0, start));
	dist[start] = 0;
	while(!pq.empty()){
		int at = pq.top().second;
		pq.pop();
		for(auto next : G[at]){
			if(dist[next.first] > dist[at] + next.second){
				dist[next.first] = dist[at] + next.second;
				pq.push(mp(-dist[next.first], next.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;
	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] = true;
			v.pb({pair1[0][i], i});
		}
	}
	sort(v.begin(), v.end());
	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: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45