Submission #388746

#	Time	Username	Problem	Language	Result	Execution time	Memory
388746		idontreallyknow	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	773 ms	57556 KiB

commuter_pass

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class A> ostream& operator<<(ostream &cout, vector<A> const &v) {cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";};
template<class A, class B> ostream& operator<<(ostream &cout, const pair<A,B> &x) {return cout << "(" <<x.first << ", " << x.second << ")";};
template<class T> void pv(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) cerr << *i << " "; cerr << "]\n";}
void _print() {cerr << "]\n";}
template<class T, class... V> void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = [", _print(x)
#define fi first
#define se second
#define SZ(x) (int)((x).size())
#define pii pair<int,int>
const int mx = 1e5+5;
const ll inf = 1e17; //change
template<class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<class T> void dijkstra(const vector<vector<pair<int,T>>>& adj, vector<T>& dist, int src) {
	fill(dist.begin(), dist.end(), inf);
	dist[src] = 0;
	vector<bool> visited(SZ(dist));
	minpq<pair<T,int>> pq;
	pq.push({0,src});
	while (SZ(pq)) {
		pair<ll,int> t = pq.top();
		pq.pop();
		if (visited[t.se]) continue;
		visited[t.se] = true;
		for (pair<int,T> p : adj[t.se]) {
			if (dist[t.se]+p.se < dist[p.fi]) {
				dist[p.fi] = dist[t.se]+p.se;
				pq.push({dist[p.fi], p.fi});
			}
		}
	}
}
template<class T> void uni(vector<T> &a) {
	sort(a.begin(), a.end());
	a.resize(unique(a.begin(), a.end()) - a.begin());
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	int s,t,u,v;
	cin >> s >> t >> u >> v;
	vector<array<ll,3>> edges;
	vector<vector<pair<int,ll>>> adj(n+1);
	for (int q = 0; q < m; q++) {
		ll a,b,c;
		cin >> a >> b >> c;
		adj[a].emplace_back(b,c);
		adj[b].emplace_back(a,c);
		edges.push_back({a,b,c});
	}
	vector<ll> sdist(n+1), tdist(n+1), udist(n+1), vdist(n+1);
	dijkstra(adj,sdist,s);
	dijkstra(adj,tdist,t);
	dijkstra(adj,udist,u);
	dijkstra(adj,vdist,v);
	vector<pair<ll,int>> on;
	vector<set<pair<int,ll>>> adj2(n+1);
	for (array<ll,3> e : edges) {
		bool zero = false;
		if (sdist[e[0]]+e[2]+tdist[e[1]] == sdist[t]) zero = true;
		if (sdist[e[1]]+e[2]+tdist[e[0]] == sdist[t]) zero = true;
		if (zero) {
			on.emplace_back(udist[e[0]],e[0]);
			on.emplace_back(udist[e[1]],e[1]);
			adj2[e[0]].insert({e[1],e[2]});
			adj2[e[1]].insert({e[0],e[2]});
		}
	}
	uni(on);
	ll ans = udist[v];
	for (int q = 0; q < SZ(on); q++) {
		ll d = on[q].fi, x = on[q].se;
		queue<pair<ll,int>> bfs;
		bfs.push({0,x});
		while (SZ(bfs)) {
			pair<ll,int> f = bfs.front();
			bfs.pop();
			ans = min(ans, d+vdist[f.se]);
			auto it = adj2[f.se].begin();
			while (it != adj2[f.se].end()) {
				auto it1 = it++;
				bool onpath = false;
				if (it1->se + f.fi+sdist[x]+tdist[it1->fi] == sdist[t]) onpath = true;
				if (it1->se + f.fi+sdist[it1->fi]+tdist[x] == sdist[t]) onpath = true;
				if (onpath) {
					bfs.push({f.fi+it1->se, it1->fi});
					adj2[f.se].erase(it1);
				}
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

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