Submission #1176640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176640		lechaa	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	235 ms	30300 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> p;
vector<bool> j;
int ans = 1e18;
vector<int> dis;
vector<int> dis1;
vector<pair<int, int>> dp;
vector<int> topo;

void dfs(int k){
	j[k] = true;
	for(int i = 0; i < p[k].size(); i++){
		topo[p[k][i]]++;
		if(j[p[k][i]]) continue;
		dfs(p[k][i]);
	}
}

main(){
	ios_base::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;
	topo.resize(n+1);
	j.resize(n+1);
	vector<vector<pair<int, int>>> g(n+1);
	for(int i = 0; i < m; i++){
		int a, b; cin >> a >> b;
		int c; cin >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}
	p.resize(n+1);
	vector<bool> d(n+1);
	vector<int> mn(n+1, 1e18);
	multiset<pair<int, int>> q;
	q.insert({0, s});
	while(!q.empty()){
		auto [time, k] = *q.begin();
		q.erase(q.begin());
		if(d[k] || k == t) continue;
		d[k] = true;
		for(auto [v, ti] : g[k]){
			if(mn[v] == ti + time){
				p[v].push_back(k);
			}
			if(d[v]) continue;
			if(mn[v] > ti + time){
				mn[v] = ti+time;
				p[v] = {k};
				q.insert({mn[v], v});
			}
		}
	}
	q.clear();
	q.insert({0, u});
	dp.resize(n+1, {1e18, 1e18});
	dis.resize(n+1, 1e18);
	dis[u] = 0;
	d.clear();
	d.resize(n+1, false);
	while(q.size() > 0){
		auto [time, k] = *q.begin();
		q.erase(q.begin());
		if(d[k]) continue;
		d[k] = true;
		for(auto [v, ti] : g[k]){
			if(d[v]) continue;
			if(dis[v] > ti + time){
				dis[v] = ti+time;
				q.insert({dis[v], v});
			}
		}
	}
	q.clear();
	q.insert({0, v});
	dis1.resize(n+1, 1e18);
	dis1[v] = 0;
	d.clear();
	d.resize(n+1, false);
	while(q.size() > 0){
		auto [time, k] = *q.begin();
		q.erase(q.begin());
		if(d[k]) continue;
		d[k] = true;
		for(auto [v, ti] : g[k]){
			if(d[v]) continue;
			if(dis1[v] > ti + time){
				dis1[v] = ti+time;
				q.insert({dis1[v], v});
			}
		}
	}
	queue<int> r;
	r.push(t);
	dfs(t);
	j.clear();
	j.resize(n+1, false);
	while(!r.empty()){
		int k = r.front();
		r.pop();
		if(j[k]) continue;
		j[k] = true;
		dp[k].first = min(dp[k].first, dis[k]);
		dp[k].second = min(dp[k].second, dis1[k]);
		for(int i = 0; i < p[k].size(); i++){
			if(j[p[k][i]]){
				continue;
			}
			topo[p[k][i]]--;
			dp[p[k][i]].first = min(min(dp[k].first, dis[k]), dp[p[k][i]].first);
			dp[p[k][i]].second = min(dp[p[k][i]].second, min(dp[k].second, dis1[k]));
			if(topo[p[k][i]] == 0){
				r.push(p[k][i]);
			}
		}
		ans = min(ans, min(dp[k].first + dis1[k], dp[k].second + dis[k]));
	}
	cout << min(ans, dis[v]) << "\n";
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main(){
      | ^~~~

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