제출 #1303229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303229		minhjulzi	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	53 ms	4968 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 ++)
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; i --)

#define bit(x, i) ((x >> i) & 1)

#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()

using ll = long long;
using pii = pair<int, int>;
// mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
// ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }
const int N = 205;
const int M = 5e4 + 5;
const ll inf = 1e18;
const int mod = 1e9 + 7;
const int base = 31;
int n, m;
ll d1[N], dn[N], dist[N][N], ans = inf;
struct node{
    int u, v, c, d;
    bool operator == (const node& a) const {
        return u == a.u && v == a.v && c == a.c && d == a.d;
    }
} ed[M];
vector<node> g[N], rev[N];
bool vis[N];
ll dijk(int s, int target, ll dist[]){
    FOR(i, 1, n) dist[i] = inf;
    memset(vis, 0, sizeof vis);
    dist[s] = 0; 
    FOR(i, 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) break;
        vis[st] = 1;
        for(auto [u, v, c, d] : g[st])
            if(dist[v] > dist[st] + c)
                dist[v] = dist[st] + c;
    }
    return dist[target];
}
void process(){
    cin>>n>>m;
    FOR(i, 1, n) FOR(j, 1, n) dist[i][j] = inf; 
    FOR(i, 1, n) dist[i][i] = 0;
    FOR(i, 1, m){
        cin>>ed[i].u>>ed[i].v>>ed[i].c>>ed[i].d;
        g[ed[i].u].pb(ed[i]);
        dist[ed[i].u][ed[i].v] = min(dist[ed[i].u][ed[i].v], ed[i].c);
    }
    FOR(k, 1, n) FOR(i, 1, n) FOR(j, 1, n) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    ans = dijk(1, n, d1) + dijk(n, 1, dn);
    FOR(i, 1, m){
        auto [u, v, c, d] = ed[i];
        if(ans > d + min(dist[1][n], dist[1][v] + dist[u][n]) + min(dist[n][1], dist[n][v] + dist[u][1]) + c){
            g[u].erase(find(g[u].begin(), g[u].end(), ed[i]));
            g[v].pb({v, u, c, d});
            ans = min(ans, dijk(1, n, d1) + dijk(n, 1, dn) + d);
            // cout<<ans<<" ";
            g[v].pop_back();
            g[u].pb(ed[i]);
        }
    }
    cout<<(ans >= inf ? -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;
    // cin>>tc;
    while(tc --) process();
    // cerr << "\nMemory: " << abs(&M2-&M1)/1024.0/1024 << " Mb\n";
    // cerr << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << " ms\n";
    return 0;
}

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

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

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