제출 #1037078

#제출 시각아이디문제언어결과실행 시간메모리
1037078ttttttttttttthCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
156 ms25932 KiB
// Author: Ivan Teo // Created: Sun Jul 28 10:10:07 2024 #define TASKNAME "joi" #include <bits/stdc++.h> using namespace std; #define fore(i, a, b) for (int i = (a); i <= (b); i++) #define ford(i, a, b) for (int i = (a); i >= (b); i--) #define int long long using vi = vector<int>; using ii = pair<int, int>; #define pb emplace_back #define fi first #define se second #define sz(v) ((int)v.size()) #define all(v) v.begin() + 1, v.end() #define alll(v) v.begin(), v.end() #define db(x) cerr << "[" << #x << " = " << x << "]" #define ell cerr << "\n=========================================\n" #define el cerr << '\n' #define Unique(v) v.erase(unique(alll(v)), v.end()) mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int l, int r) { assert(l <= r); return uniform_int_distribution<int> (l, r)(rng); } template<int D, typename T> struct Vec : public vector < Vec < D - 1, T >> { template<typename... Args> Vec(int n = 0, Args... args) : vector < Vec < D - 1, T >> (n, Vec < D - 1, T > (args...)) {} }; template<typename T> struct Vec<1, T> : public vector<T> { Vec(int n = 0, const T &val = T()) : vector<T>(n, val) {} }; template<class T>void minimize(T &a, T b) { if(a > b) { a = b; } } const int INF = 1e18; const int N = 1e5 + 5; vector<pair<int, int>>e[N]; void dijkstra(int vertex, vector<int> &d) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq; pq.emplace(d[vertex] = 0, vertex); bitset<N>vis; while(!pq.empty()) { auto [w, u] = pq.top(); pq.pop(); if(w == d[u]) { for(auto& [v, edge_w] : e[u]) { int W = w + edge_w; if(W < d[v]) { pq.emplace(d[v] = W, v); } } } } } void ivan() { int n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; for(int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; e[a].emplace_back(b, c); e[b].emplace_back(a, c); } vector<int>d_s(n + 1, INF), d_u(n + 1, INF), d_v(n + 1, INF), dp_u(n + 1, INF), dp_v(n + 1, INF); dijkstra(s, d_s); dijkstra(u, d_u); dijkstra(v, d_v); int ans = d_u[v]; function<void(int)>dfs; dfs = [&] (int vertex) { if(dp_u[vertex] != INF) { return; } dp_u[vertex] = d_u[vertex]; dp_v[vertex] = d_v[vertex]; for(auto& [next_vertex, w] : e[vertex]) { if(d_s[next_vertex] + w == d_s[vertex]) { dfs(next_vertex); minimize(dp_u[vertex], dp_u[next_vertex]); minimize(dp_v[vertex], dp_v[next_vertex]); } } minimize(ans, min(dp_v[vertex] + d_u[vertex], dp_u[vertex] + d_v[vertex])); }; dfs(t); cout << ans; } signed main() { cin.tie(0)->sync_with_stdio(0); if (fopen(TASKNAME".inp", "r")) { freopen(TASKNAME".inp", "r", stdin); freopen(TASKNAME".out", "w", stdout); } int tc = 1; // cin >> tc; while (tc--) ivan(); el, cerr << "Execution Time: " << 1.0 * clock() / CLOCKS_PER_SEC << "s", el; return 0; }

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(TASKNAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(TASKNAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...