제출 #380338

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380338		randomjohnnyh	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	452 ms	17276 KiB

commuter_pass

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <sstream>
#include <random>
using namespace std;

#define range1(n) for (int __i = 0, __n = int(n); __i < __n; ++__i)
#define range2(i, n) for (int i = 0, __n = int(n); i < __n; ++i)
#define range3(i, a, b) for (int i = int(a), __b = int(b); i < __b; ++i)
#define range4(i, a, b, c) for (int i = int(a), __b = int(b); (c > 0) ? (i < __b) : (i > __b); i += c)
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define range(...) GET_MACRO(__VA_ARGS__, range4, range3, range2, range1)(__VA_ARGS__)
#define each2(a, v) for (auto&& a : v)
#define each3(a, b, v) for (auto&& [a, b] : v)
#define each4(a, b, c, v) for (auto&& [a, b, c] : v)
#define each(...) GET_MACRO(__VA_ARGS__, each4, each3, each2, each1)(__VA_ARGS__)
#define iterate(i, a, v) for (auto [it, __end, i] = std::tuple{begin(v), end(v), 0}; it != __end; it++, i++) if (auto&& a = *it; true)
#define len(v) ((int)(v).size())
#define pb push_back
#define all(v) begin(v), end(v)
#define getindex(f,v,...) int(f(all(v),##__VA_ARGS__) - begin(v))
#define endl '\n';
#ifdef DEBUG
#define dprint(a) print(a)
#else
#define dprint(a)
#endif


template <typename U, typename T1, typename T2>
U& operator>>(U& is, std::pair<T1, T2>& p) { return is >> p.first >> p.second; }
template <typename U, typename T, typename enable_if<!is_same<T,string>::value>::type* = nullptr>
U& operator>>(U& is, T& a) { for (auto&& e : a) { is >> e; } return is; }
template <typename U, typename T1, typename T2>
U& operator<<(U& os, const std::pair<T1, T2>& p) { return os << p.first << " " << p.second; }
template <typename U, typename T, typename enable_if<!is_same<T,string>::value>::type* = nullptr>
U& operator<<(U& os, const T& a) { bool f = true; for (auto&& e : a) { if (f) f = false; else os << " "; os << e; } return os; }
template<typename T> void read(T& value) { cin >> value; }
template<typename T, typename... Args> void read(T& value, Args&&... args) { cin >> value; read(forward<Args>(args)...); }
void print() { cout << endl; }
template<typename T, typename... Args> void print(const T& value) { cout << value; print(); }
template<typename T, typename... Args> void print(const T& value, Args&&... args) { cout << value << " "; print(forward<Args>(args)...); }
template <typename T> bool setmin(T& a, const T& b) { if (b < a) {a = b; return true;} return false; }
template <typename T> bool setmax(T& a, const T& b) { if (b > a) {a = b; return true;} return false; }
template <typename T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <typename T> int sign(T a) { return a < 0 ? -1 : (a > 0 ? 1 : 0); }
template <typename T> T square(T a) { return a * a; }
template <typename T> void sortunique(T& v) { sort(all(v)); v.erase(unique(all(v)), v.end()); }
template <typename T, typename U=typename T::value_type, typename O=less<U>> vector<int> argsort(const T& v, const O& op = O()) { vector<int> w(len(v)); iota(all(w), 0); sort(all(w), [&](int a, int b) {return v[a] != v[b] ? op(v[a], v[b]) : a < b;}); return w; }
vector<int> invert(const vector<int>& v) { vector<int> w(len(v)); range(i, len(v)) { w[v[i]] = i; } return w; }
template <typename T, typename U=typename T::value_type, typename O=plus<U>> vector<U> prefixes(const T& v, const O& op = O()) { vector<U> sums(len(v)+1); partial_sum(all(v), ++sums.begin(), op); return sums; }
template <typename T, typename U=typename T::value_type> map<U, int> counter(const T& v) { map<U, int> f; for (auto&& e : v) { f[e]++; }; return f; }
template <typename T, typename U=typename T::value_type, typename O=equal_to<U>> vector<pair<U, int> > groupby(const T& v, const O& op = O()) {vector<pair<U, int> > w; for(auto&& a : v) {if (not w.empty() and op(a, w.back().first)) {w.back().second++; } else {w.emplace_back(a, 1); } } return w; }
template <typename Key, typename Value> const Value& getdefault(const map<Key, Value>& m, const Key& key, const Value& default_value) { auto it = m.find(key); if (it == m.end()) {return default_value; } return it->second; }
template <typename Key, typename Value> Value& getdefault(map<Key, Value>& m, const Key& key, Value& default_value) { auto it = m.find(key); if (it == m.end()) {return default_value; } return it->second; }
string OK(bool a) { return a ? "YES" : "NO"; }
string Ok(bool a) { return a ? "Yes" : "No"; }

template<class Fun>
class y_combinator_result {
  Fun fun_;
public:
  template<class T>
  explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

  template<class ...Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;

const double pi = acos(-1.0);
constexpr ll inf = (int)1e9 + 7;

void solve()
{
	int n, m;
	read(n, m);
	vector<vector<pii> > adj(n);
	int s, t;
	read(s, t);
	s--; t--;
	int u, v;
	read(u, v);
	u--; v--;
	range(m) {
		int a, b, c;
		read(a, b, c);
		a--; b--;
		adj[a].pb({b, c});
		adj[b].pb({a, c});
	}
	auto dijkstra = [&](vector<vector<pii> >& g, int a) {
		typedef pair<ll,int> point;
		vector<ll> dist(n, inf * inf);
		priority_queue<point, vector<point>, greater<point> > pq;
		dist[a] = 0;
		pq.push({0ll, a});
		while (not pq.empty()) {
			auto [d, cur] = pq.top(); pq.pop();
			if (d != dist[cur]) continue;
			for (auto [nxt, w] : g[cur]) {
				if (setmin(dist[nxt], d + w)) {
					pq.push({dist[nxt], nxt});
				}
			}
		}
		return dist;
	};
	auto distS = dijkstra(adj, s);
	auto distT = dijkstra(adj, t);
	auto distU = dijkstra(adj, u);
	auto distV = dijkstra(adj, v);
	ll totDist = distS[t];
	ll ans = inf * inf;
	{
		auto ordS = argsort(distS);
		auto dp = distU;
		each(a, ordS) {
			for (auto&& [b, w] : adj[a]) {
				if (distS[a] + w + distT[b] == totDist) {
					setmin(dp[b], dp[a]);
				}
			}
		}
		range(i, n) {
			setmin(ans, distV[i] + dp[i]);
		}
	}
	{
		auto ordT = argsort(distT);
		auto dp = distU;
		each(a, ordT) {
			for (auto&& [b, w] : adj[a]) {
				if (distT[a] + w + distS[b] == totDist) {
					setmin(dp[b], dp[a]);
				}
			}
		}
		range(i, n) {
			setmin(ans, distV[i] + dp[i]);
		}
	}
	print(ans);
}

void go()
{
	int testn = 1;
	// read(testn);
	for (int testi = 1; testi <= testn; testi++)
	{
		solve();
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(10);
	cout << setfill('0');
	go();
}

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

commuter_pass.cpp: In lambda function:
commuter_pass.cpp:118:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |    auto [d, cur] = pq.top(); pq.pop();
      |         ^
commuter_pass.cpp:120:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |    for (auto [nxt, w] : g[cur]) {
      |              ^
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:138:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |    for (auto&& [b, w] : adj[a]) {
      |                ^
commuter_pass.cpp:152:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  152 |    for (auto&& [b, w] : adj[a]) {
      |                ^

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