Submission #400148

#	Time	Username	Problem	Language	Result	Execution time	Memory
400148		SavicS	Olympic Bus (JOI20_ho_t4)	C++14	37 / 100	1055 ms	2012 KiB

ho_t4

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const ll inf = 1e18 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, m;
array<int,4> niz[maxn];

bool used[maxn];

const int N = 205;
vector<int> g[N];
vector<int> rg[N];

int len[maxn];
ll dist[2][N]; // 0 - 1, 1 - n
int from[2][N]; // 0 - 1, 1 - n
void dij1(int s, ll dist[], int from[]){
    ff(i,1,n)dist[i] = inf, len[i] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    pq.push({dist[s] = 0, s});
    while(!pq.empty()){
        pii v = pq.top(); pq.pop();
        if(dist[v.se] < v.fi)continue;
        for(int c : g[v.se]){
            int u = niz[c][1];
            int w = niz[c][2];
            if(v.se != niz[c][0])continue;
            if(dist[u] > w + v.fi){
                pq.push({dist[u] = w + v.fi, u});
                from[u] = c;
                len[u] = len[v.se] + 1;
                continue;
            }
            if(dist[u] == w + v.fi){
                if(len[v.se] + 1 < len[u])from[u] = c;
            }
        }
    }

}

ll rdist[2][N]; // 0 - 1, 1 - n
void dij2(int s, ll dist[]){
    ff(i,1,n)dist[i] = inf;
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    pq.push({dist[s] = 0, s});
    while(!pq.empty()){
        pii v = pq.top(); pq.pop();
        if(dist[v.se] < v.fi)continue;
        for(int c : rg[v.se]){
            int u = niz[c][0];
            int w = niz[c][2];
            if(dist[u] > w + v.fi){
                pq.push({dist[u] = w + v.fi, u});
            }
        }
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cin >> n >> m;
    ff(i,1,m){
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        g[u].pb(i);
        rg[v].pb(i);
        niz[i] = {u, v, c, d};
    }

    dij1(1, dist[0], from[0]), dij1(n, dist[1], from[1]);
    dij2(1, rdist[0]), dij2(n, rdist[1]);

    int cur = n;
    while(from[0][cur] && cur != 1){
        used[from[0][cur]] = 1;
        cur = niz[from[0][cur]][0];
    }

    cur = 1;
    while(from[1][cur] && cur != n){
        used[from[1][cur]] = 1;
        cur = niz[from[1][cur]][0];
    }

    ll rez = inf;
    rez = min(rez, dist[0][n] + dist[1][1]);
    ff(i,1,m){
        int u = niz[i][0];
        int v = niz[i][1];
        int c = niz[i][2];
        int d = niz[i][3];
        if(!used[i]){

            ll A = min(dist[0][n], dist[0][v] + c + rdist[1][u]);
            ll B = min(dist[1][1], dist[1][v] + c + rdist[0][u]);

            rez = min(rez, A + B + d);

        }

    }

    ff(i,1,m){
        int u = niz[i][0];
        int v = niz[i][1];
        int c = niz[i][2];
        int d = niz[i][3];
        if(used[i]){
            swap(niz[i][0], niz[i][1]);
            g[v].pb(i);
            dij1(1, dist[0], from[0]), dij1(n, dist[1], from[1]);
            g[v].pop_back();
            swap(niz[i][0], niz[i][1]);

            rez = min(rez, dist[0][n] + d + dist[1][1]);

        }
    }

    cout << (rez == inf ? -1 : rez);

    return 0;
}
/**

4 4
1 2 0 4
1 3 0 1
4 3 0 2
4 1 0 1


4 4
1 2 1 0
2 3 1 0
2 4 3 0
3 4 2 0

// probati bojenje sahovski ili slicno

**/

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:133:13: warning: unused variable 'u' [-Wunused-variable]
  133 |         int u = niz[i][0];
      |             ^
ho_t4.cpp:135:13: warning: unused variable 'c' [-Wunused-variable]
  135 |         int c = niz[i][2];
      |             ^

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