제출 #1259241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259241		wedonttalkanymore	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	24 ms	5960 KiB

ho_t4

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

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 400 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 16;

int n, m;
struct item {
    int v, c, d, id;
};
struct node {
    int u, v, c, d;
} a[100005];
vector <item> adj[N], adj1[N];
pii edge[N][N];
int length[N];
bool check1[100005], check2[100005];
int road1[100005], road2[100005];
int dist[N][N];

void dijk(int u, vector <pii> &trace, int cant) {
    for (int i = 1; i <= n; i++) {
        length[i] = inf;
        trace[i] = make_pair(0, 0);
    }
    length[u] = 0;
    priority_queue <pii, vector <pii>, greater <pii> > q;
    q.push({0, u});
    while(q.size()) {
        auto [val, u] = q.top();
        q.pop();
        if (val > length[u]) continue;
        for (auto [v, c, d, id] : adj[u]) {
            if (id == cant) continue;
            if (length[v] > length[u] + c) {
                length[v] = length[u] + c;
                trace[v] = {u, id};
                q.push({length[v], v});
            }
        }
    }
}

void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

signed main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) if (i != j) dist[i][j] = inf;
    }
    for (int i = 1; i <= m; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        a[i] = {u, v, c, d};
        adj[u].push_back({v, c, d, i});
        dist[u][v] = min(dist[u][v], c);
    }
    floyd();

    for (int i = 1; i <= m; i++) check1[i] = check2[i] = false;

    vector <pii> trace1(n + 1, make_pair(0, 0));
    dijk(1, trace1, -1);
    int minn = length[n];
    int t = n;
    while(t > 0) {
        auto [v, id] = trace1[t];
        if (v == 0) break;
        check1[id] = true;
        t = v;
    }

    vector <pii> trace2(n + 1, make_pair(0, 0));
    dijk(n, trace2, -1);
    int minn2 = length[1];
    t = 1;
    while(t > 0) {
        auto [v, id] = trace2[t];
        if (v == 0) break;
        check2[id] = true;
        t = v;
    }

    for (int i = 1; i <= m; i++) {
        if (check1[i]) dijk(1, trace1, i), road1[i] = length[n];
        else road1[i] = minn;
    }
    for (int i = 1; i <= m; i++) {
        if (check2[i]) dijk(n, trace2, i), road2[i] = length[1];
        else road2[i] = minn2;
    }

    int ans = inf;
    if (dist[1][n] < inf && dist[n][1] < inf) ans = min(ans, dist[1][n] + dist[n][1]);
    for (int i = 1; i <= m; i++) if (road1[i] < inf && road2[i] < inf) ans = min(ans, road1[i] + road2[i]);

    for (int i = 1; i <= m; i++) {
        int u = a[i].u, v = a[i].v, c = a[i].c, d = a[i].d;
        int val1 = inf, val2 = inf;
        if (dist[1][v] < inf && dist[u][n] < inf) val1 = dist[1][v] + c + dist[u][n];
        if (dist[n][v] < inf && dist[u][1] < inf) val2 = dist[n][v] + c + dist[u][1];

        if (val1 < inf && road2[i] < inf) ans = min(ans, val1 + road2[i] + d);
        if (val2 < inf && road1[i] < inf) ans = min(ans, road1[i] + val2 + d);
    }

    if (ans >= inf / 2) cout << -1 << '\n';
    else cout << ans << '\n';

    return 0;
}

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

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63