제출 #388669

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
388669		S2speed	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	551 ms	36920 KiB

commuter_pass

#include<bits/stdc++.h>
#include<fstream>
 
using namespace std;
 
#pragma GCC optimize ("Ofast")
 
#define all(x) x.begin() , x.end()
#define mp make_pair
#define gcd __gcd
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<ll , pll> plll;
typedef pair<pii , int> piii;
typedef pair<pll , pll> pllll;
 
const ll maxn = 2e5 + 16 , md = 1e9 + 7 , inf = 2e18;

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

ll n , m , a[4];
ll dis[maxn][4] , dp[maxn][2] , ans = inf;
priority_queue<pll , vector<pll> , greater<pll>> pq;
vector<pll> adj[maxn] , o;
vector<ll> sdj[maxn];
bitset<maxn> mark;

void dij(ll j){
	mark.reset();
	dis[a[j]][j] = 0;
	pq.push({0 , a[j]});
	while(!pq.empty()){
		pll p = pq.top(); pq.pop();
		ll v = p.second;
		if(mark[v]) continue;
		mark[v] = true;
		for(auto p : adj[v]){
			ll i = p.first , w = p.second;
			if(dis[i][j] < dis[v][j] + w) continue;
			dis[i][j] = dis[v][j] + w;
			pq.push({dis[i][j] , i});
		}
	}
	return;
}

int main(){ // check MAXN
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(dis , 63 , sizeof(dis));
	cin>>n>>m>>a[0]>>a[1]>>a[2]>>a[3]; a[0]--; a[1]--; a[2]--; a[3]--;
	for(ll i = 0 ; i < m ; i++){
		ll v , u , w;
		cin>>v>>u>>w; v--; u--;
		adj[v].push_back({u , w}); adj[u].push_back({v , w});
	}
	for(ll j = 0 ; j < 4 ; j++){
		dij(j);
	}
	for(ll v = 0 ; v < n ; v++){
		for(auto p : adj[v]){
			ll i = p.first , w = p.second;
			if(dis[v][0] + dis[i][1] + w == dis[a[1]][0]){
				sdj[i].push_back(v);
			}
		}
	}
	for(ll i = 0 ; i < n ; i++){
		o.push_back({dis[i][0] , i});
	}
	sort(all(o));
	for(ll e = 0 ; e < n ; e++){
		ll v = o[e].second;
		dp[v][0] = dis[v][2];
		dp[v][1] = dis[v][3];
		for(auto i : sdj[v]){
			dp[v][0] = min(dp[v][0] , dp[i][0]);
			dp[v][1] = min(dp[v][1] , dp[i][1]);
		}
		ans = min(ans , min(dp[v][0] + dis[v][3] , dp[v][1] + dis[v][2]));
	}
	cout<<ans<<'\n';
	return 0;
}

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