Submission #888895

#	Time	Username	Problem	Language	Result	Execution time	Memory
888895		hariaakas646	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1057 ms	3932 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);

    int curr = 1;
    int k = 0;
    if(dist[1][n] < 1e16)
    {
        while(curr != n) {
            bool done = false;
            for(auto e : graph[curr]) {
                if(vec[e].c + dist[vec[e].v][n] == dist[vec[e].u][n] && vec[e].c != 0) {
                    curr = vec[e].v;
                    inpath[e] = true;
                    done = true;
                    break;
                }
            }
            if(!done) {
                for(auto e : graph[curr]) {
                    if(vec[e].c + dist[vec[e].v][n] == dist[vec[e].u][n]) {
                        curr = vec[e].v;
                        inpath[e] = true;
                        done = true;
                        break;
                    }
                }
            }
            if(!done) break;
            
        }
        
    }

    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(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];
        }
        mi = min(mi, v);
    }

    inpath = vb(m);

    curr = n;
    k = 0;
    if(dist[n][1] < 1e16) 
    {
        while(curr != 1) {
            bool done = false;
            for(auto e : graph[curr]) {
                if(vec[e].c + dist[vec[e].v][1] == dist[vec[e].u][1] && vec[e].c != 0) {
                    curr = vec[e].v;
                    inpath[e] = true;
                    done = true;
                    break;
                }
            }
            if(!done) {
                for(auto e : graph[curr]) {
                    if(vec[e].c + dist[vec[e].v][1] == dist[vec[e].u][1]) {
                        curr = vec[e].v;
                        inpath[e] = true;
                        done = true;
                        break;
                    }
                }
            }
            if(!done) break;
            
        }
        
    }

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

        if(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, 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 += dist2[1];
            graph[p.v].erase(i);
            graph[p.u].insert(i);

            swap(vec[i].u, vec[i].v);
        }
        else {
            v += dist[n][1];
        }
        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:78:9: warning: variable 'k' set but not used [-Wunused-but-set-variable]
   78 |     int k = 0;
      |         ^
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