제출 #1367959

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

commuter_pass

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 1e5;
const int maxm = 2e5;
const ll INF = 1e18;

int n, m, S, T, U, V;
ll d[305][305];
vector <pair<int, int>> adj[maxn+5];

void read() {
    cin >> n >> m;
    cin >> S >> T;
    cin >> U >> V;
    for (int i = 1; i<=m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
}

void FW() {
    for (int i = 1; i<=n; ++i) {
        for (int j = 1; j<=n; ++j)
            d[i][j] = (i != j ? INF : 0);
    }

    for (int u = 1; u<=n; ++u) {
        for (pair <int, int> e : adj[u]) {
            int v = e.first, w = e.second;
            d[u][v] = min(d[u][v], 1LL * w);
            d[v][u] = min(d[v][u], 1LL * w);
        }
    }

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

void sub3() {
    FW();
    ll res = INF;
    for (int L = 1; L<=n; ++L) {
        for (int R = 1; R<=n; ++R) {
            if (d[L][R] + d[S][L] + d[R][T] == d[S][T]) {
                res = min(res, d[U][L] + d[R][V]);
                res = min(res, d[V][L] + d[R][U]);
            }
        }
    }
//    cout << (d[1][2] + d[5][1] + d[7][2] == d[5][7] ? "YES" : "NO");
//    cout << d[2][6] + d[1][8];
    cout << min(res, d[U][V]);
}

void solve() {
    if (n <= 300) sub3();
}

int main() {

    freopen("commuter_pass.inp", "r", stdin);
    freopen("commuter_pass.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    read();
    solve();

    return 0;
}

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

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:71:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     freopen("commuter_pass.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:72:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     freopen("commuter_pass.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 0 / 16
• 서브태스크 2: 0 / 15
• 서브태스크 3: 0 / 24
• 서브태스크 4: 0 / 45