제출 #830317

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

commuter_pass

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//turn on extra precision
//#pragma GCC target("fpmath=387")

using namespace std;
using namespace __gnu_pbds;

using str   = string;
using ll    = long long;
using pii   = pair <int,int>;
using pll   = pair <ll,ll>;
using vi    = vector <int>;
using vll   = vector <ll>;
using vpii  = vector <pii>;
using vpll  = vector <pll>;

template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T> &v) {
    bool van = 1; os << '{';
    for(auto &i : v) { if(!van) os << ", "; os << i; van = 0; }
    os << '}'; return os;
}

template<class T, size_t sz>
ostream& operator<<(ostream&os, const array<T,sz> &arr) {
    bool fs = 1; os << '{';
    for(auto &i : arr) { if(!fs) os << ", "; os << i; fs = 0; }
    os << '}'; return os;
}

#define mp make_pair
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'
#define all(x) x.begin(), x.end()
#define watch(x) cerr << (#x) << " is : " << (x) << newl

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
ll quickpow(ll num1, ll num2, const T MOD) {
    assert(num2 >= 0); ll ans = 1;
    for(; num2; num2>>=1, num1 = num1 * num1 % MOD) if(num2 & 1) ans = ans * num1 % MOD;
    return ans;
}
// end of Template

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;

    vector<vector<pair<int,int>>> adj(n+1);
    for(int a, b, c; m--; ) {
        cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    const ll INF = 1e17;
    vector<vector<ll>> dist(4, vector<ll>(n+1, INF));

    const auto dijkstra = [&n, &adj](vector<ll> &dist, int x) -> void {
        vector<bool> vis(n+1);
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;

        q.emplace(0, x);
        dist[x] = 0;

        for(; !q.empty(); ) {
            auto [d, node] = q.top();
            q.pop();
            if(vis[node]) continue;
            vis[node] = true;
            for(auto &[nex, c] : adj[node]) {
                if(dist[nex] > dist[node] + c) {
                    dist[nex] = dist[node] + c;
                    q.emplace(dist[nex], nex);
                }
            }
        }
    };

    dijkstra(dist[0], s);
    dijkstra(dist[1], t);
    dijkstra(dist[2], u);
    dijkstra(dist[3], v);

    ll ans = dist[2][v], opt = dist[0][t];
    const auto solve = [&](int x, int y) -> void {
        priority_queue <pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
        for(int i = 1; i <= n; ++i) q.emplace(dist[0][i], i);
        vector<ll> dp(n+1, INF);

        for(; !q.empty();) {
            auto [d, i] = q.top();
            q.pop();

            if(dist[0][i] + dist[1][i] != opt) continue;
            dp[i] = dist[x][i];
            for(auto &[nex, c] : adj[i]) {
                if(dist[0][i] == dist[0][nex] + c) {
                    dp[i] = min(dp[i], dp[nex]);
                }
            }

            ans = min(ans, dp[i] + dist[y][i]);
        }
    };
    solve(2, 3);
    solve(3, 2);

    cout << ans << newl;

    return 0;
}

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

commuter_pass.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
commuter_pass.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
commuter_pass.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    8 | #pragma comment(linker, "/stack:200000000")
      |

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