Submission #889225

#	Time	Username	Problem	Language	Result	Execution time	Memory
889225		hariaakas646	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	1078 ms	4308 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;


void usaco()
{
    freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
//    freopen("problem.out", "w", stdout);
}

struct Edge {
    int u, v, c, d;
};

int main() {
    // usaco();
    int n, m;
    scd(n);
    scd(m);

    vector<Edge> vec(m);

    vector<seti> graph(n+1);

    vector<vll> dist(n+1, vll(n+1, 1e17));

    forr(i, 1, n+1) dist[i][i] = 0;

    frange(i, m) {
        int u, v, c, d;
        scd(u);
        scd(v);
        scd(c);
        scd(d);
        vec[i].u = u;
        vec[i].v = v;
        vec[i].c = c;
        vec[i].d = d;

        dist[u][v] = min(dist[u][v], (lli)c);
        graph[u].insert(i);
    }

    forr(k, 1, n+1) {
        forr(i, 1, n+1) {
            forr(j, 1, n+1) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    vb inpath(m);

    queue<pii> q;
    q.push(mp(1, -10));
    vi par(n+1, -1);
    if(dist[1][n] < 1e16)
    {
        while(q.size()) {
            auto p = q.front();
            q.pop();
            if(par[p.f] != -1) continue;
            par[p.f] = p.s;

            if(p.f == n) {
                int curr = n;
                while(curr != 1) {
                    // printf("%d ", curr);
                    inpath[par[curr]] = true;
                    curr = vec[par[curr]].u;
                }
            }

            for(auto e : graph[p.f]) {
                if(dist[1][vec[e].u] + vec[e].c + dist[vec[e].v][n] == dist[1][n]) {
                    q.push(mp(vec[e].v, e));
                }
            }
        }
        
    }

    lli mi = dist[1][n] + dist[n][1];

    // frange(i, m) {
    //     auto p = vec[i];
    //     lli v = dist[n][p.v] + dist[p.u][1] + p.c + p.d;

    //     if(v + dist[1][n] < mi) {
    //         graph[p.u].erase(i);
    //         graph[p.v].insert(i);

    //         swap(vec[i].u, vec[i].v);
    
    //         vll dist2(n+1, 1e16);
    //         priority_queue<pair<lli, int>> pq;
    //         pq.push(mp(0, 1));
    //         dist2[1] = 0;
    //         vb vis(n+1);
    //         while(pq.size()) {
    //             auto p = pq.top();
    //             pq.pop();
    
    //             if(vis[p.s]) continue;
    //             vis[p.s] = true;
    
    //             for(auto j : graph[p.s]) {
    //                 auto e = vec[j];
    //                 if(dist2[p.s] + e.c < dist2[e.v]) {
    //                     dist2[e.v] = dist2[p.s] + e.c;
    //                     pq.push(mp(-dist2[e.v], e.v));
    //                 }
    //             }
    //         }
    //         v += dist2[n];
    //         graph[p.v].erase(i);
    //         graph[p.u].insert(i);
    //         mi = min(mi, v);
    //         swap(vec[i].u, vec[i].v);
    //     }
    //     // else {
    //     //     v += dist[1][n];
    //     // }
    //     // mi = min(mi, v);
    // }

    vb inpath2(m);

    q = {};
    q.push(mp(n, -10));
    par = vi(n+1, -1);
    if(dist[n][1] < 1e16)
    {
        while(q.size()) {
            auto p = q.front();
            q.pop();
            if(par[p.f] != -1) continue;
            par[p.f] = p.s;

            if(p.f == 1) {
                int curr = 1;
                while(curr != n) {
                    // printf("%d ", curr);
                    inpath2[par[curr]] = true;
                    curr = vec[par[curr]].u;
                }
            }

            for(auto e : graph[p.f]) {
                if(dist[n][vec[e].u] + vec[e].c + dist[vec[e].v][1] == dist[n][1]) {
                    q.push(mp(vec[e].v, e));
                }
            }
        }
        
    }

    frange(i, m) {
        auto p = vec[i];
        // lli v = min(dist[1][n], dist[1][p.v] + dist[p.u][n] + p.c) + p.d;

        lli d1 = min(dist[1][n], dist[1][p.v] + dist[p.u][n] + p.c);
        lli d2 = min(dist[n][1], dist[n][p.v] + dist[p.u][1] + p.c);

        lli v = p.d;
        if(dist[1][p.v] + dist[p.u][n] + p.c < dist[1][n] || inpath[i]) {
            graph[p.u].erase(i);
            graph[p.v].insert(i);

            swap(vec[i].u, vec[i].v);
    
            vll dist2(n+1, 1e16);
            priority_queue<pair<lli, int>> pq;
            pq.push(mp(0, 1));
            dist2[1] = 0;
            vb vis(n+1);
            while(pq.size()) {
                auto p = pq.top();
                pq.pop();
    
                if(vis[p.s]) continue;
                vis[p.s] = true;
    
                for(auto j : graph[p.s]) {
                    auto e = vec[j];
                    if(dist2[p.s] + e.c < dist2[e.v]) {
                        dist2[e.v] = dist2[p.s] + e.c;
                        pq.push(mp(-dist2[e.v], e.v));
                    }
                }
            }
            v += dist2[n];

            graph[p.v].erase(i);
            graph[p.u].insert(i);

            swap(vec[i].u, vec[i].v);
        }
        else v += dist[1][n];

        if(dist[n][p.v] + dist[p.u][1] + p.c < dist[n][1] || inpath2[i]) {
            graph[p.u].erase(i);
            graph[p.v].insert(i);

            swap(vec[i].u, vec[i].v);
    
            vll dist2(n+1, 1e16);
            priority_queue<pair<lli, int>> pq;
            pq.push(mp(0, n));
            dist2[n] = 0;
            vb vis(n+1);
            while(pq.size()) {
                auto p = pq.top();
                pq.pop();
    
                if(vis[p.s]) continue;
                vis[p.s] = true;
    
                for(auto j : graph[p.s]) {
                    auto e = vec[j];
                    if(dist2[p.s] + e.c < dist2[e.v]) {
                        dist2[e.v] = dist2[p.s] + e.c;
                        pq.push(mp(-dist2[e.v], e.v));
                    }
                }
            }
            v += min(dist2[1], dist[n][p.v] + dist[p.u][1] + p.c);

            graph[p.v].erase(i);
            graph[p.u].insert(i);
            swap(vec[i].u, vec[i].v);
        }
        else v += dist[n][1];

        
        // else {
        //     v += dist[n][1];
        // }
        mi = min(mi, v);
    }

    // frange(i, m) {
    //     auto p = vec[i];
    //     lli v = dist[1][p.v] + dist[p.u][n] + p.c + p.d + dist[n][p.v] + dist[p.u][1] + p.c;
    //     mi = min(mi, v);
    // }

    if(mi < 1e16) printf("%lld", mi);
    else printf("-1");

}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:185:13: warning: unused variable 'd1' [-Wunused-variable]
  185 |         lli d1 = min(dist[1][n], dist[1][p.v] + dist[p.u][n] + p.c);
      |             ^~
ho_t4.cpp:186:13: warning: unused variable 'd2' [-Wunused-variable]
  186 |         lli d2 = min(dist[n][1], dist[n][p.v] + dist[p.u][1] + p.c);
      |             ^~
ho_t4.cpp: In function 'void usaco()':
ho_t4.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:41:5: note: in expansion of macro 'scd'
   41 |     scd(n);
      |     ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:42:5: note: in expansion of macro 'scd'
   42 |     scd(m);
      |     ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:54:9: note: in expansion of macro 'scd'
   54 |         scd(u);
      |         ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:55:9: note: in expansion of macro 'scd'
   55 |         scd(v);
      |         ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:56:9: note: in expansion of macro 'scd'
   56 |         scd(c);
      |         ^~~
ho_t4.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
ho_t4.cpp:57:9: note: in expansion of macro 'scd'
   57 |         scd(d);
      |         ^~~

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