Submission #1158767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158767		Nurlykhan	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	389 ms	28376 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const int N = (int)2e5 + 10;
const long long LINF = (long long) 1e18;

int n, m;
int s, t, u, v;
long long d[4][N];

vector<pair<long long, int> > g[N];

pair<long long, int> ord[N];
long long dp[N][4];


void djikstra(int type, int s_point) {
    for (int i = 1; i <= n; i++) {
        d[type][i] = LINF;
    }
    d[type][s_point] = 0;

    set<pair<long long, int> > st;
    st.insert(make_pair(d[type][s_point], s_point));
    while (!st.empty()) {
        int cur = st.begin()->second;
        st.erase(st.begin());
        for (auto go : g[cur]) {
            if (d[type][cur] + go.second < d[type][go.first]) {
                st.erase(make_pair(d[type][go.first], go.first));
                d[type][go.first] = d[type][cur] + go.second;
                st.insert(make_pair(d[type][go.first], go.first));
            }
        }
    }
}

int main() {
    #ifdef local
        freopen("input.txt", "r", stdin);
    #endif // local

    scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);

    while (m--) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);

        g[x].push_back(make_pair(y, c));
        g[y].push_back(make_pair(x, c));
    }

    djikstra(0, s);
    djikstra(1, t);
    djikstra(2, u);
    djikstra(3, v);

    long long ans = d[2][v];

    ans = min(ans, d[2][s] + d[1][v]); // u->s...t->v
    ans = min(ans, d[2][t] + d[0][v]); // u->t...s->v

    for (int i = 1; i <= n; i++) {
        ord[i] = make_pair(d[0][i], i);

        dp[i][1] = LINF;
        dp[i][2] = LINF;
        dp[i][3] = LINF;
    }
    sort(ord + 1, ord + n + 1);
    for (int ptr = 1; ptr <= n; ptr++) {
        int i = ord[ptr].second;

        // cout << "ptr " << ptr << " ord " << i << "\n";
        if (d[0][i] + d[1][i] == d[0][t]) {
            dp[i][1] = d[2][i];
            dp[i][2] = d[3][i];
            dp[i][3] = d[2][i] + d[3][i];
            for (auto it : g[i]) {
                if (d[0][it.first] + it.second == d[0][i]) {
                    dp[i][1] = min(dp[it.first][1], dp[i][1]);
                    dp[i][2] = min(dp[it.first][2], dp[i][2]);
                    dp[i][3] = min(dp[it.first][3], dp[i][3]);

                    dp[i][3] = min(d[2][i] + dp[it.first][2], dp[i][3]);
                    dp[i][3] = min(d[3][i] + dp[it.first][1], dp[i][3]);


                }
            }
        }

        ans = min(ans, dp[i][3]);
    }
    cout << ans;

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%d%d%d", &x, &y, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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