제출 #407044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407044		evilbuggy	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	855 ms	25636 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const int M = 200005;
const long long inf = (long long)1e18;
vector<int> g[N];
int a[M], b[M], c[M], vis[N];
long long dists[N], distt[N];
long long distu[N], distv[N];
long long pref[N], suff[N];

inline void distances(int n, long long dist[], int s){
	for(int i = 1; i <= n; i++){
		dist[i] = inf;
		vis[i] = 0;
	}
	set<pair<long long, int> > st;
	st.insert({0, s});
	dist[s] = 0;
	while(!st.empty()){
		auto pp = *st.begin();
		int u = pp.second;
		st.erase(pp);
		if(vis[u])continue;
		vis[u] = 1;
		for(int i : g[u]){
			int v = a[i]^b[i]^u;
			if(dist[v] > dist[u] + c[i]){
				dist[v] = dist[u] + c[i];
				st.insert({dist[v], v});
			}
		}
	}
}

long long compute(int n, int s, int t, int flg){
	vector<pair<long long, int> > vec;
	for(int i = 1; i <= n; i++){
		pref[i] = dists[i];
		suff[i] = distt[i];
		if(flg){
			pref[i] += distu[i];
			suff[i] += distv[i];
		}else{
			pref[i] += distv[i];
			suff[i] += distu[i];
		}
		vec.push_back({dists[i], i});
	}
	sort(vec.begin(), vec.end());
	for(auto pp : vec){
		int u = pp.second;
		for(int i : g[u]){
			int v = a[i]^b[i]^u;
			if(dists[u] + c[i] + distt[v] == dists[t]){
				pref[v] = min(pref[v], pref[u] + c[i]);
			}
		}
	}
	reverse(vec.begin(), vec.end());
	for(auto pp : vec){
		int u = pp.second;
		for(int i : g[u]){
			int v = a[i]^b[i]^u;
			if(dists[v] + c[i] + distt[u] == dists[t]){
				suff[v] = min(suff[v], suff[u] + c[i]);
			}
		}
	}
	long long ret = inf;
	for(int i = 1; i <= n; i++){
		ret = min(ret, pref[i] + suff[i]);
	}
	return ret;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	cin >> n >> m;
	int s, t;
	cin >> s >> t;
	int u, v;
	cin >> u >> v;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i] >> c[i];
		g[a[i]].push_back(i);
		g[b[i]].push_back(i);
	}
	distances(n, dists, s);
	distances(n, distt, t);
	distances(n, distu, u);
	distances(n, distv, v);
	long long ans = inf;
	ans = min(ans, compute(n, s, t, 0));
	ans = min(ans, compute(n, s, t, 1));
	ans = min(ans - dists[t], distu[v]);
	cout << ans << '\n';

	return 0;
}

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