제출 #1259251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259251		wedonttalkanymore	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	23 ms	5448 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 = 200 + 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 check[100005], check1[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();
//        cout << u << ' ' << val << '\n';
        if (val > length[u]) continue;
        for (auto [v, c, d, id] : adj[u]) {
            if (id == cant) continue;
//        	cout << v << ' ' << length[v] << '\n';
            if (length[v] > length[u] + c) {
//            	cout << u << ' ' << v << ' ';
                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();
    vector <pii> trace1(n + 1, make_pair(0, 0));
//    cout << 1 << flush;
    dijk(1, trace1, -1);
    int minn = length[n];
    int t = n;
    while(t > 0) {
    	// cout << t << ' ';
        auto [v, id] = trace1[t];
        if (v == 0) break;
        check[id] = true;
        t = v;
    }
    for (int i = 1; i <= m; i++) {
        if (check[i]) {
            dijk(1, trace1, i);
            road1[i] = length[n];
        }
        else road1[i] = minn;
    }
    dijk(n, trace1, -1);
    int minn2 = length[1];
    t = 1;
    while(t > 0) {
    	// cout << t << ' ';
        auto [v, id] = trace1[t];
        if (v == 0) break;
        check1[id] = true;
        t = v;
    }
    // cout << minn << ' ' << minn2 << '\n';
    for (int i = 1; i <= m; i++) {
        if (check1[i]) {
            dijk(n, trace1, i);
            // cout << "ch: " << i << ' ' << length[1] << '\n';
            road2[i] = length[1];
        }
        else road2[i] = minn2;
    }
    // cout << dist[1][3] << '\n';
    // for (int i = 1; i <= m; i++) cout << road1[i] << ' ' << road2[i] << '\n';
    // cout << "ok: ";
    // for (int i = 1; i <= m; i++) cout << check[i] << ' ';
    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 && dist[n][1] < inf) ans = min(ans, (val1 + road2[i] + d));
        if (val2 < inf && dist[1][n] < inf) ans = min(ans, (road1[i] + val2 + d));
    }

    if (ans >= inf) cout << -1;
    else cout << ans;

    return 0;
}

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

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

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