Submission #684205

#	Time	Username	Problem	Language	Result	Execution time	Memory
684205		fuad27	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	306 ms	24228 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
const int N=100'010;
vector<array<long long, 2>> g[N];
int n, m;
vector<long long> dist(int s) {
	priority_queue<pair<long long, long long>> pq;
	vector<bool> vis(n);
	vector<long long> d(n,1e18);
	pq.push({0,s});
	d[s]=0;
	while(pq.size()) {
		int at=pq.top().second;
		pq.pop();
		if(vis[at])continue;
		vis[at]=1;
		for(auto to:g[at]) {
			if(d[to[0]]>d[at]+to[1]) {
				d[to[0]]=d[at]+to[1];
				pq.push({-d[to[0]],to[0]});
			}
		}
	}
	return d;
}
int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	int S, T, U, V;
	cin >> S >> T >> U >> V;
	S--,T--,U--,V--;
	for(int i = 0;i<m;i++) {
		long long a, b, c;
		cin >> a >> b >> c;
		a--,b--;
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	vector<long long> s=dist(S), t=dist(T), u=dist(U), v=dist(V);
	long long dpu[n], dpv[n];
	dpu[0]=dpv[0]=1e18;
	vector<pair<long long, int>> is;
	for(int i = 0;i<n;i++) {
		dpu[i]=dpv[i]=1e18;
		if(s[i]+t[i]==s[T]){
			is.push_back({s[i],i});
		}
	}
	sort(is.begin(), is.end());
	long long res=1e18;
	for(auto [asdf,i]:is) {
		dpu[i]=u[i];
		dpv[i]=v[i];
		for(auto to:g[i]) {
			if(t[i]+to[1]+s[to[0]]==s[T]) {
				dpu[i]=min(dpu[i],dpu[to[0]]);
				dpv[i]=min(dpv[i],dpv[to[0]]);
			}
		}
		res=min(res,dpu[i]+v[i]);
		res=min(res,u[i]+dpv[i]);
	}
	res=min(res,u[V]);
	cout << res << endl;
	return 0;
}

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