Submission #1158761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158761		Nurlykhan	Commuter Pass (JOI18_commuter_pass)	C++20	24 / 100	31 ms	3656 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

    scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = LINF;
        }
        d[i][i] = 0;
    }
    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));

        d[x][y] = min(d[x][y], 1LL * c);
        d[y][x] = min(d[y][x], 1LL * c);
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

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

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

    for (int i = 1; i <= n; i++) {
        ord[i] = make_pair(d[s][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[s][i] + d[i][t] == d[s][t]) {
            dp[i][1] = d[u][i];
            dp[i][2] = d[v][i];
            dp[i][3] = d[u][i] + d[v][i];
            for (auto it : g[i]) {
                if (d[s][it.first] + it.second == d[s][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[u][i] + dp[it.first][2], dp[i][3]);
                    dp[i][3] = min(d[v][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:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d%d%d%d%d%d", &n, &m, &s, &t, &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d%d%d", &x, &y, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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