Submission #1273694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273694		icebear	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	16 ms	1980 KiB

ho_t4

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

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 1e5 + 5;
int n, m, a[N], b[N], c[N], d[N];
vector<int> G[2][N];
bool in_path[N];
ll dist[2][2][N], tmp[N];
int par[N], edge[N];

void dijkstra(int s, ll dist[N], const vector<int> *G) {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> Q;
    fill(dist, dist + n + 1, INF);
    fill(par, par + n + 1, 0);
    Q.push(mp(0, s));
    dist[s] = 0;

    while(!Q.empty()) {
        int u; ll du;
        tie(du, u) = Q.top(); Q.pop();
        if (du != dist[u]) continue;
        for(int i : G[u]) {
            int v = a[i] ^ b[i] ^ u;
            if (minimize(dist[v], dist[u] + c[i])) {
                par[v] = u;
                edge[v] = i;
                Q.push(mp(dist[v], v));
            }
        }
    }

    for(int t = n; t; t = par[t]) in_path[edge[t]] = true;
}

ll calcDist(int s, int id, ll dist[N]) {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> Q;
    fill(dist, dist + n + 1, INF);
    Q.push(mp(0, s));
    dist[s] = 0;

    while(!Q.empty()) {
        ll du; int u;
        tie(du, u) = Q.top(); Q.pop();
        if (du != dist[u]) continue;
        for(int i : G[0][u]) {
            if (id == i) continue;
            int v = a[i] ^ b[i] ^ u;
            if (minimize(dist[v], dist[u] + c[i]))
                Q.push(mp(dist[v], v));
        }

        int v = b[id];
        if (u == a[id] && minimize(dist[v], dist[u] + c[id])) Q.push(mp(dist[v], v));
     }
     return dist[s == 1 ? n : 1];
}

void init(void) {
    cin >> n >> m;
    FOR(i, 1, m) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        G[0][a[i]].pb(i);
        G[1][b[i]].pb(i);
    }
}

void process(void) {
    dijkstra(1, dist[0][0], G[0]); dijkstra(n, dist[0][1], G[0]);
    dijkstra(n, dist[1][0], G[1]); dijkstra(1, dist[1][1], G[1]);


    ll ans = min(INF, dist[0][0][n] + dist[0][1][1]);

    FOR(i, 1, m) {
        if (in_path[i]) minimize(ans, calcDist(1, i, tmp) + calcDist(n, i, tmp) + d[i]);
        else {
            int u = a[i], v = b[i];
            ll dist1 = min(dist[0][0][n], dist[0][0][v] + dist[1][0][u] + c[i]);
            ll dist2 = min(dist[0][1][1], dist[0][1][v] + dist[1][1][u] + c[i]);
            minimize(ans, dist1 + dist2 + d[i]);
        }
    }
    cout << (ans == INF ? -1 : ans);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//    cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}

Compilation message (stderr)

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

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