Submission #1176573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176573		lechaa	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	444 ms	60008 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> p;
vector<bool> j;
map<pair<int, int>, bool> b; 

void dfs(int k){
	j[k] = true;
	for(int i = 0; i < p[k].size(); i++){
		b[{p[k][i], k}] = true;
		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;
	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, 1e9);
	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});
			}
		}
	}
	dfs(t);
	q.clear();
	q.insert({0, u});
	vector<int> dis(n+1, 1e18);
	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(b[{k, v}]){
				ti = 0;
			}
			if(dis[v] > ti + time){
				dis[v] = ti+time;
				q.insert({dis[v], v});
			}
		}
	}
	q.clear();
	q.insert({0, u});
	vector<int> dis1(n+1, 1e18);
	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(b[{v, k}]){
				ti = 0;
			}
			if(dis1[v] > ti + time){
				dis1[v] = ti+time;
				q.insert({dis1[v], v});
			}
		}
	}
	cout << min(dis[v], dis1[v]) << "\n";
	return 0;
}

Compilation message (stderr)

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

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