제출 #415147

#제출 시각아이디문제언어결과실행 시간메모리
415147meatrowCommuter Pass (JOI18_commuter_pass)C++17
31 / 100
862 ms27452 KiB
// #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int MOD = 1e9 + 7; ll binpow(ll a, ll p, int mod = MOD) { ll res = 1; while (p) { if (p & 1) { (res *= a) %= mod; } p >>= 1; (a *= a) %= mod; } return res; } ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } void solve() { int n, m; int S, T; int U, V; cin >> n >> m >> S >> T >> U >> V; vector<vector<pair<int, ll>>> g(n + 1); for (int i = 0; i < m; i++) { int a, b; ll c; cin >> a >> b >> c; g[a].emplace_back(b, c); g[b].emplace_back(a, c); } auto getDist = [&](int from) { vector<ll> dist(n + 1, 1e18); dist[from] = 0; set<pair<ll, int>> setik; setik.insert({0, from}); while (!setik.empty()) { int v = setik.begin()->second; setik.erase(setik.begin()); for (auto& [u, w] : g[v]) { if (dist[v] + w < dist[u]) { setik.erase({dist[u], u}); dist[u] = dist[v] + w; setik.insert({dist[u], u}); } } } return dist; }; vector<ll> distS = getDist(S); vector<ll> distT = getDist(T); vector<ll> distU = getDist(U); vector<ll> distV = getDist(V); ll ans = distU[V]; vector<int> used(n + 1); vector<ll> dp(n + 1), pd(n + 1); function<void(int)> dfs = [&](int v) { used[v] = 1; dp[v] = distV[v]; pd[v] = distU[v]; for (auto& [u, w] : g[v]) { if (used[u] || distS[v] + w + distT[u] > distS[T]) continue; dfs(u); dp[v] = min(dp[v], dp[u]); pd[v] = min(pd[v], pd[u]); } ans = min(ans, distU[v] + dp[v]); ans = min(ans, distV[v] + pd[v]); }; dfs(S); cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; for (int tc = 1; tc <= T; tc++) { // cout << "Case #" << tc << ": "; solve(); } return 0; }

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

commuter_pass.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...