제출 #400172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
400172		SavicS	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1022 ms	1924 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 = 5e10 + 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;
int A[maxn];
int B[maxn];
int C[maxn];
int D[maxn];

bool used[maxn];

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

ll duz[2][N];
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;
    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 = B[c];
            int w = C[c];
            if(v.se != A[c])continue;
            if(dist[u] > w + v.fi){
                pq.push({dist[u] = w + v.fi, 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 = A[c];
            int w = C[c];
            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);
        A[i] = u, B[i] = v, C[i] = c, D[i] = 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 = A[from[0][cur]];
    }

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

    ll rez = dist[0][n] + dist[1][1];
    ff(i,1,m){
        int u = A[i];
        int v = B[i];
        int c = C[i];
        int d = D[i];
        if(!used[i]){

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

            rez = min(rez, X + Y + d);

        }
        else{
            swap(A[i], B[i]);
            g[v].pb(i);
            dij1(1, duz[0], from[0]), dij1(n, duz[1], from[1]);
            g[v].pop_back();
            swap(A[i], B[i]);

            rez = min(rez, duz[0][n] + d + duz[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

**/

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