제출 #678612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678612		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	342 ms	31460 KiB

commuter_pass

/*
	Unknown's C++ Template (v3.2)
*/

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

#define int long long

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
template <class T> using maxpq = priority_queue<T>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mid ((l+r)>>1)
#define fi first
#define se second

#ifdef LOCAL
	#define debug(x) cout << #x << " = " << x << "\n";
#else
	#define debug(x) ;
#endif

template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x)
{ out << "(" << x.first << ", " << x.second << ")"; return out; }

template <class T>
ostream& operator << (ostream& out, vector<T> x){
	out << "[";
	for (int i=0; i<sz(x); i++) { out << (i ? ", " : "") << x[i]; }
	out << "]"; return out;
}

template <class T>
istream& operator >> (istream& in, vector<T> &x){
	for (auto &i: x) in >> i;
	return in;
}

const ld PI = acos(-1.0);
const int allmod[3] = {(int)1e9+7, 998244353, (int)1e9+9};
const int mod = allmod[0];
const int maxn = 2e5 + 64;
const ll inf = 1e18;
const ld eps = 1e-6;
const int multitest = 0;

int n, m;
int s, t, a, b;
vi dist_u, dist_v, dist_s, dist_t;
vi dps, dpt;
vector<pair<ii, int>> edges;
vvii adj, dag;

void dfs(int x){
	dps[x] = dist_s[x];
	dpt[x] = dist_t[x];
	for (auto [k, w]: dag[x]){
		if (dps[k] == inf+1) dfs(k);
		dps[x] = min(dps[x], dps[k]);
		dpt[x] = min(dpt[x], dpt[k]);
	}
}

void main_program(){
	cin >> n >> m;
	cin >> s >> t >> a >> b;
	s--; t--; a--; b--;

	dist_u.assign(n, inf); dist_v.assign(n, inf);
	dist_s.assign(n, inf); dist_t.assign(n, inf);
	edges.resize(m);
	adj.resize(n); dag.resize(n);
	dps.assign(n, inf+1);
	dpt.assign(n, inf+1);

	for (int i = 0; i < m; i++){
		int x, y, w; cin >> x >> y >> w;
		x--; y--;

		edges[i] = {{x, y}, w};
		adj[x].emplace_back(y, w);
		adj[y].emplace_back(x, w);
	}

	// debug(adj);

	//=== DIJKSTRA FROM U ===//
	{
		minpq<ii> q; q.emplace(0, s); dist_u[s] = 0;
		while (!q.empty()){
			auto [d, x] = q.top(); q.pop();
			if (dist_u[x] != d) continue;

			for (auto [k, w]: adj[x]){
				if (dist_u[k] > d + w){
					dist_u[k] = d + w;
					q.emplace(d + w, k);
				}
			}
		}
		// debug(dist_u);
	}

	//=== DIJKSTRA FROM V ===//
	{
		minpq<ii> q; q.emplace(0, t); dist_v[t] = 0;
		while (!q.empty()){
			auto [d, x] = q.top(); q.pop();
			if (dist_v[x] != d) continue;

			for (auto [k, w]: adj[x]){
				if (dist_v[k] > d + w){
					dist_v[k] = d + w;
					q.emplace(d + w, k);
				}
			}
		}
		// debug(dist_v);
	}

	//=== DIJKSTRA FROM S ===//
	{
		minpq<ii> q; q.emplace(0, a); dist_s[a] = 0;
		while (!q.empty()){
			auto [d, x] = q.top(); q.pop();
			if (dist_s[x] != d) continue;

			for (auto [k, w]: adj[x]){
				if (dist_s[k] > d + w){
					dist_s[k] = d + w;
					q.emplace(d + w, k);
				}
			}
		}
		// debug(dist_s);
	}

	//=== DIJKSTRA FROM T ===//
	{
		minpq<ii> q; q.emplace(0, b); dist_t[b] = 0;
		while (!q.empty()){
			auto [d, x] = q.top(); q.pop();
			if (dist_t[x] != d) continue;

			for (auto [k, w]: adj[x]){
				if (dist_t[k] > d + w){
					dist_t[k] = d + w;
					q.emplace(d + w, k);
				}
			}
		}
		// debug(dist_t);
	}

	int sp = dist_u[t];

	for (auto [e, w]: edges){
		int i, j; tie(i, j) = e;
		if (dist_u[i] + w + dist_v[j] == sp) dag[i].emplace_back(j, w);
		if (dist_u[j] + w + dist_v[i] == sp) dag[j].emplace_back(i, w);
	}

	// debug(dag);

	dfs(s);
	// debug(dps); debug(dpt);

	int res = dist_s[b];
	for (int i = 0; i < n; i++) res = min(res, dist_s[i] + dpt[i]);
	for (int i = 0; i < n; i++) res = min(res, dist_t[i] + dps[i]);

	cout << res << "\n";
}

void pre_main(){

}

signed main(){
	#ifdef LOCAL
		auto stime = chrono::high_resolution_clock::now();
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#ifndef ONLINE_JUDGE
		if (fopen(".inp", "r")){
			freopen(".inp", "r", stdin);
			freopen(".out", "w", stdout);
		}
	#endif
	int T = 1; if (multitest) cin >> T;
	pre_main();
	while (T--) main_program();
	#ifdef LOCAL
		auto etime = chrono::high_resolution_clock::now();
		auto duration = chrono::duration_cast<chrono::milliseconds>(etime-stime).count();
		cout << "\n[" << duration << "ms]\n";
	#endif
}

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:197:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  197 |    freopen(".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:198:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |    freopen(".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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