Submission #1268437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268437		CodeLakVN	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	155 ms	1956 KiB

ho_t4

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

#define task "main"
#define F first
#define S second
#define ii pair<int, int>
#define il pair<int, long long>
#define li pair<long long, int>
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)

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

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

template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }

const int MAX_N = (int)203;
const int MAX_M = (int)5e4+ 4;
const long long INF = (long long)1e18;

int nNode, nEdge;
long long firstMin[MAX_N][MAX_N], secondMin[MAX_N][MAX_N];

struct EDGE {
    int u, v, cost, revCost;
} edges[MAX_M];

long long dist[2][MAX_N], revDist[2][MAX_N], tmpDist[2][MAX_N];
bool isKey[MAX_N][MAX_N], visited[MAX_N], used[MAX_N][MAX_N];
int parent[MAX_N];

void dijkstra(int u, long long *d, short type) {
    FOR(i, 0, nNode) d[i] = INF, parent[i] = 0, visited[i] = false;
    d[u] = 0;
    while (true) {
        int u = 0;
        FOR(i, 1, nNode) if (!visited[i] && d[i] < d[u])
            u = i;
        if (!u) break;

        visited[u] = true;
        FOR(v, 1, nNode) if (!visited[v])
            if (minimize(d[v], d[u] + (type == 1 ? firstMin[v][u] : firstMin[u][v])))
                if (type < 2)
                    parent[v] = u;
    }

    if (type < 2) {
        FOR(u, 1, nNode) isKey[parent[u]][u] = true;
    }
}

void solve() {
    memset(firstMin, 0x3f, sizeof(firstMin));
    memset(secondMin, 0x3f, sizeof(secondMin));

    cin >> nNode >> nEdge;
    FOR(i, 1, nEdge) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        if (firstMin[u][v] > c) {
            secondMin[u][v] = firstMin[u][v];
            firstMin[u][v] = c;
        }
        else if (secondMin[u][v] > c)
            secondMin[u][v] = c;
        edges[i] = {u, v, c, d};
    }

    dijkstra(1, dist[0], 0);
    dijkstra(nNode, dist[1], 0);
    dijkstra(1, revDist[0], 1); // 1: reverse edges
    dijkstra(nNode, revDist[1], 1);

    long long ans = dist[0][nNode] + dist[1][1];

    FOR(i, 1, nEdge) {
        auto [u, v, cost, changeCost] = edges[i];
        if (!used[u][v] && isKey[u][v] && cost == firstMin[u][v]) {
            used[u][v] = true;

            // reverse edge u->v
            long long preUV = firstMin[u][v], preVU = firstMin[v][u];
            minimize(firstMin[v][u], cost);
            firstMin[u][v] = secondMin[u][v];

            dijkstra(1, tmpDist[0], 2);
            dijkstra(nNode, tmpDist[1], 2);

            minimize(ans, tmpDist[0][nNode] + tmpDist[1][1] + changeCost);

            firstMin[u][v] = preUV, firstMin[v][u] = preVU;
        }
        else {
            minimize(ans, changeCost + min(dist[0][nNode], dist[0][v] + cost + revDist[1][u]) +
                                     min(dist[1][1], revDist[0][u] + cost + dist[1][v]));
        }
    }

    cout << (ans >= INF ? -1 : ans);
}

int32_t main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    bool multitest = 0;
    int numTest = 1;
    if (multitest) cin >> numTest;

    while (numTest--) {
        solve();
    }

    return 0;
}

/* Lak lu theo dieu nhac!!!! */

Compilation message (stderr)

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

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