Submission #852907

#	Time	Username	Problem	Language	Result	Execution time	Memory
852907		Mr_Husanboy	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	82 ms	10604 KiB

commuter_pass

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



#ifdef LOCAL
#include "debugger.cpp"
#else
#define debug(...)
#endif
template<class T>
int len(T &a){
	return a.size();
}

using ll = long long;
using pii = pair<int,int>;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
string fileio = "";


mt19937 mt(time(nullptr));
const int mod = 1e9 + 7;
const int inf = 1e9;
const ll infl = 1e18;
const int maxn = 1e5 + 1;





void solve(){
	int n, m; cin >> n >> m;
	int s, t, lef, rig; cin >> s >> t >> lef >> rig;
	s --, t --, lef --, rig --;

	vector<vector<pair<int,int>>> g(n);
	for(int i = 0; i < n; i ++){
		int w;
		int u, v; cin >> u >> v;
		cin >> w;
		u --; v --;
		g[u].push_back({v, w});
		g[v].emplace_back(u, w);
	}
	vector<ll> ds(n, infl), dt(n, infl);
	{
		
		priority_queue<pair<int, ll>> q;
		vector<int> vis(n);
		ds[s] = 0;
		q.push({0, s});
		while(!q.empty()){
			int v = q.top().second;
			q.pop();
	
			if(vis[v]) continue;
			vis[v] = 1;
			for(auto [u, w] : g[v]){
				if(ds[u] > ds[v] + w){
					ds[u] = ds[v] + w;
					q.push({-ds[u], u});
				}
			}
		}
	}
	{
		
		priority_queue<pair<int, ll>> q;
		vector<int> vis(n);
		q.push({0, t});
		dt[t] = 0;
		while(!q.empty()){
			int v = q.top().second;
			q.pop();
	
			if(vis[v]) continue;
			vis[v] = 1;
			for(auto [u, w] : g[v]){
				if(dt[u] > dt[v] + w){
					dt[u] = dt[v] + w;
					q.push({-dt[u], u});
				}
			}
		}
	}

	vector<ll> dl(n, infl), dr(n, infl);

	{
		
		priority_queue<pair<int, ll>> q;
		vector<int> vis(n);
		q.push({0, lef});
		dl[lef] = 0;
		while(!q.empty()){
			int v = q.top().second;
			q.pop();
			if(vis[v]) continue;
			vis[v] = 1;
			for(auto [u, w] : g[v]){
				//if(min(dt[u], dt[v]) + min(ds[u], ds[v]) + w == dt[s]) w = 0;
				if(dl[u] > dl[v] + w){
					dl[u] = dl[v] + w;
					q.push({-dl[u], u});
				}
			}
		}
	}
	{
		
		priority_queue<pair<int, ll>> q;
		vector<int> vis(n);
		q.push({0, rig});
		dr[rig] = 0;
		while(!q.empty()){
			int v = q.top().second;
			q.pop();
			if(vis[v]) continue;
			vis[v] = 1;
			for(auto [u, w] : g[v]){
				//if(min(dt[u], dt[v]) + min(ds[u], ds[v]) + w == dt[s]) w = 0;
				if(dr[u] > dr[v] + w){
					dr[u] = dr[v] + w;
					q.push({-dr[u], u});
				}
			}
		}
	}

	ll mr = infl, ml = infl;
	for(int i = 0;i < n; i ++){
		if(ds[i] + dt[i] == dt[s]){
			ml = min(dl[i], ml);
			mr = min(dr[i], mr);
		}
	}

	cout << ml + mr;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	auto start = chrono::high_resolution_clock::now();
	#ifndef LOCAL
	if(fileio.size()){
		freopen((fileio + ".in").c_str(), "r", stdin);
		freopen((fileio + ".out").c_str(), "w", stdout);
	}
	#endif
	int testcases = 1;
	#ifdef Tests
	cin >> testcases;
	#endif
	while(testcases --){
		solve();
		cout << '\n';
		#ifdef LOCAL
		cout << "_________________________" << endl;
		#endif
	}
	#ifdef LOCAL
	auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
	
	cout << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
	#endif
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:146:7: warning: variable 'start' set but not used [-Wunused-but-set-variable]
  146 |  auto start = chrono::high_resolution_clock::now();
      |       ^~~~~
commuter_pass.cpp:149:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |   freopen((fileio + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:150:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |   freopen((fileio + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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