제출 #1303213

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303213		minhjulzi	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	54 ms	4976 KiB

ho_t4

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

#define int long long
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i ++)

using ll = long long;

const int MAXN = 205;
const ll inf = (ll)4e18;

int n, m;
ll d1[MAXN], dn[MAXN], distFW[MAXN][MAXN], ans = inf;

struct node{
    int u, v;
    ll c, d;
    bool operator == (const node& a) const {
        return u == a.u && v == a.v && c == a.c && d == a.d;
    }
};

vector<node> ed;   
vector<node> g[MAXN];
bool vis[MAXN];

ll dijk(int s, int target, ll dist[]){
    FOR(i, 1, n) dist[i] = inf;
    memset(vis, 0, sizeof vis);
    dist[s] = 0;

    FOR(it, 1, n){
        int st = -1;
        FOR(j, 1, n) if(!vis[j] && (st == -1 || dist[st] > dist[j])) st = j;
        if(st == -1 || dist[st] >= inf/2) break;

        vis[st] = 1;
        for(auto e : g[st]){
            int v = e.v;
            ll c = e.c;
            if(dist[v] > dist[st] + c) dist[v] = dist[st] + c;
        }
    }
    return dist[target];
}

void process(){
    cin >> n >> m;

    FOR(i, 1, n) g[i].clear();

    ed.assign(m + 1, node());

    // init Floyd matrix
    FOR(i, 1, n) FOR(j, 1, n) distFW[i][j] = inf;
    FOR(i, 1, n) distFW[i][i] = 0;

    FOR(i, 1, m){
        cin >> ed[i].u >> ed[i].v >> ed[i].c >> ed[i].d;
        g[ed[i].u].push_back(ed[i]);
        distFW[ed[i].u][ed[i].v] = min(distFW[ed[i].u][ed[i].v], ed[i].c);
    }

    FOR(k, 1, n) FOR(i, 1, n) FOR(j, 1, n){
        if(distFW[i][k] >= inf/2 || distFW[k][j] >= inf/2) continue;
        distFW[i][j] = min(distFW[i][j], distFW[i][k] + distFW[k][j]);
    }

    ll go = dijk(1, n, d1);
    ll back = dijk(n, 1, dn);
    ans = go + back;

    FOR(i, 1, m){
        auto [u, v, c, d] = ed[i];

        ll best1 = min(distFW[1][n], distFW[1][v] + distFW[u][n]);
        ll best2 = min(distFW[n][1], distFW[n][v] + distFW[u][1]);

        if(best1 >= inf/2 || best2 >= inf/2) continue;

        if(ans > d + best1 + best2 + c){
            auto it = find(g[u].begin(), g[u].end(), ed[i]);
            if(it == g[u].end()) continue;
            g[u].erase(it);

            g[v].push_back({v, u, c, d});

            ll cand1 = dijk(1, n, d1);
            ll cand2 = dijk(n, 1, dn);
            if(cand1 < inf/2 && cand2 < inf/2) ans = min(ans, cand1 + cand2 + d);

            g[v].pop_back();
            g[u].push_back(ed[i]);
        }
    }

    cout << (ans >= inf/2 ? -1 : ans);
}

bool M2;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    #define task "task"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
    while(tc--) process();
    return 0;
}

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

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

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