Submission #1158702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158702		Nurlykhan	Commuter Pass (JOI18_commuter_pass)	C++20	24 / 100	28 ms	1148 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];

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);

        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++) {
        for (int j = 1; j <= n; j++) {
            if (d[s][t] == d[s][i] + d[i][j] + d[j][t]) { // check i is on the path from s->i->t
                ans = min(ans, d[u][i] + d[j][v]);
                ans = min(ans, d[v][i] + d[j][u]);
            }
        }
    }
    cout << ans;

    return 0;
}

Compilation message (stderr)

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

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