제출 #1181970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181970		anteknne	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	360 ms	22912 KiB

commuter_pass

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

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define pil pair<ll, ll>
#define pli pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 100 * 1000 + 1;
vector<pil> graf[MAXN];
ll odl[MAXN];
ll odlS[MAXN];
ll odlT[MAXN];
ll odlU[MAXN];
ll odlV[MAXN];
ll dp[MAXN][4];
vector<pli> vec;
priority_queue<pil> pq;

void djikstra (ll s) {
    memset(odl, ll(INT_MAX) * ll(MAXN), sizeof(odl));

    /*for (int i = 1; i <= 8; i ++) {
        cout << odl[i] << " ";
    }*/

    odl[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        ll v = pq.top().nd;
        ll vodl = -pq.top().st;
        pq.pop();
        if (vodl > odl[v]) {
            continue;
        }
        for (auto x : graf[v]) {
            if (vodl + x.nd < odl[x.st]) {
                odl[x.st] = vodl + x.nd;
                pq.push({-odl[x.st], x.st});
            }
        }
    }
}

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll n, m, S, T, U, V;
    cin >> n >> m >> S >> T >> U >> V;

    ll a, b;
    ll c;
    for (ll i = 0; i < m; i ++) {
        cin >> a >> b >> c;
        graf[a].pb({b, c});
        graf[b].pb({a, c});
    }

    djikstra(S);
    swap(odl, odlS);
    djikstra(T);
    swap(odl, odlT);
    djikstra(U);
    swap(odl, odlU);
    djikstra(V);
    swap(odl, odlV);

    if (debug) {
        cout << "odlS:\n";
        for (ll i = 1; i <= n; i ++) {
            cout << i << ": " << odlS[i] << "\n";
        }
        cout << "\n";
    }

    for (ll i = 1; i <= n; i ++) {
        vec.pb({odlS[i], i});
    }

    sort(vec.begin(), vec.end());

    memset(dp, ll(INT_MAX) * ll(MAXN), sizeof(dp));
    dp[S][0] = 0;
    dp[S][1] = odlU[S];
    dp[S][2] = odlV[S];
    dp[S][3] = odlU[S] + odlV[S];

    for (auto x : vec) {
        ll v = x.nd;
        for (auto x : graf[v]) {
            if (odlS[v] == odlS[x.st] + x.nd) {
                for (ll i = 0; i < 4; i ++) {
                    for (ll j = 0; j < 4; j ++) {
                        ll dod = 0;
                        if (j & 1) {
                            dod += odlU[x.st];
                        }
                        if (j & 2) {
                            dod += odlV[x.st];
                        }
                        dp[v][i | j] = min(dp[v][i | j], dp[x.st][i] + dod);
                    }
                }
            }
        }
    }

    cout << min(dp[T][3], odlU[V]) << "\n";



    return 0;
}

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

commuter_pass.cpp: In function 'void djikstra(ll)':
commuter_pass.cpp:33:29: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '214750512183647' to '2147383647' [-Woverflow]
   33 |     memset(odl, ll(INT_MAX) * ll(MAXN), sizeof(odl));
      |                 ~~~~~~~~~~~~^~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:95:28: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '214750512183647' to '2147383647' [-Woverflow]
   95 |     memset(dp, ll(INT_MAX) * ll(MAXN), sizeof(dp));
      |                ~~~~~~~~~~~~^~~~~~~~~~

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