Submission #1167755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167755		spycoderyt	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	162 ms	8360 KiB

ho_t4

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
#define int long long 
const int N = 305;
const int M = 60005;
multiset<pair<int,int> > A[N],B[N]; // actual and transpose
pair<int,int> edges[M];
const int inf = 1e12;
// int st[N],en[N],str[N],enr[N];
int weight[M],d[M];
int dis[4][N]; // st en str enr
int tmp[N];
int opt[2][N];
void djik(int u,int k) {
    priority_queue<pair<int,int> > pq; // -w, i
    pq.push({0,u});
    while(!pq.empty()) {
        auto [w,i] = pq.top();pq.pop();
        w*=-1;
        if(w>dis[k][i])continue;
        for(auto [nxt,ei] : (k <= 1 ? A[i] : B[i])) {
            if(dis[k][nxt] > w + weight[ei]) {
                dis[k][nxt] = w + weight[ei];
                if(k<=1){
                    opt[k][nxt] = ei;
                }
                pq.push({-dis[k][nxt], nxt});
            }
        }
    }
}
/*
what if theres multiple paths with same length possible?
*/
int djik2(int st, int en){
    priority_queue<pair<int,int> > pq; // -w, i
    pq.push({0,st});
    for(int i = 0;i<N;i++) tmp[i]=inf;
    tmp[st]=0;
    while(!pq.empty()) {
        auto [w,i] = pq.top();pq.pop();
        w*=-1;
        if(w>tmp[i])continue;
        for(auto [nxt,ei] : A[i]) {
            if(tmp[nxt] > w + weight[ei]) {
                tmp[nxt] = w + weight[ei];
                pq.push({-tmp[nxt], nxt});
            }
        }
    }
    return tmp[en];
}
int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m,a,b,ans=inf;
    cin >> n >> m;
    if(n==1){
        cout << 0;
        return 0;
    }
    for(int i = 0;i<N;i++) for(int j = 0;j<4;j++)dis[j][i]=inf;
    dis[0][1] = dis[2][1] = 0;
    dis[1][n] = dis[3][n] = 0;
    for(int i = 1;i<=m;i++) {
        cin >> a >> b >> weight[i] >> d[i];
        A[a].insert({b,i});
        B[b].insert({a,i});
        edges[i] = {a,b};
    }
    djik(1,0);
    djik(n,1);
    djik(1,2);
    djik(n,3);
    // for(int j = 0;j<4;j++) {
    //     for(int i = 1;i<=n;i++) cerr << dis[j][i] << " ";
    //     cerr << "\n";
    // }
    int x = n;
    set<int> frontpath,backpath;
    while(x!=1){
        if(opt[0][x] == 0) break;
        else {
            int ei = opt[0][x];
            x = edges[ei].f ^ edges[ei].s ^ x;
            frontpath.insert(ei);
        }
    }
    x = 1;
    while(x!=n) {
        if(opt[1][x] == 0) break;
        else {
            int ei = opt[1][x];
            x = edges[ei].f ^ edges[ei].s ^ x;
            backpath.insert(ei);
        }
    }
    // for each edge in frontpath, find 1 -> n without using that edge
    // map<int,int> frontlen,backlen;
    // for(auto e : frontpath) {
    //     djik2(1,n,e,frontlen);
    // }
    // for(auto e : backpath) {
    //     djik2(n,1,e,backlen);
    // }
    // for(auto e : frontpath) cerr << e << " ";
    // cerr<<"\n";
    // for(auto [a,b] : frontlen) cerr << a << " " << b << "\n";
    int front = dis[0][n], back = dis[1][1];
    // cerr << front << " " << back << "\n";
    ans = min(ans,front+back);
    for(int i = 1;i<=m;i++) {
        // st en str enr
        // invert first pass: st[a] + enr[b] + w + d, if m!+ then bck
        // if m in the thing then do it
        a = edges[i].f, b = edges[i].s;
        int cur;
        // edge originally from a to b
        // flip, now its b to a
        if(backpath.count(i)){
            A[a].erase(A[a].find({b,i}));
            A[b].insert({a,i});
            cur += djik2(n,1) + djik2(1,n);
            A[a].insert({b,i});
            A[b].erase(A[b].find({a,i}));
        }else cur = back + dis[0][b] + dis[3][a] + weight[i] + d[i]; // front
        ans = min(ans,cur);
        if(frontpath.count(i)) {
            A[a].erase(A[a].find({b,i}));
            A[b].insert({a,i});
            cur += djik2(1,n) + djik2(n,1);
            A[a].insert({b,i});
            A[b].erase(A[b].find({a,i}));
        }else cur = front + dis[1][b] + dis[2][a] + weight[i] + d[i];
        ans = min(ans,cur);
    }
    cout << (ans >= inf ? -1 : ans);
}

/*


        // if(dis[0][a] > dis[0][b])swap(a,b);
        int cur;
        // cur = dis[0][a] + dis[3][b] + weight[i] + d[i];
        // if(backpath.find(i) != backpath.end()) {
        //     cur += backlen[i];
        // } else cur += back;
        // ans = min(ans, cur);
        // // inverst second pass

        cur = dis[1][b] + dis[2][a] + weight[i] + d[i];
        if(frontpath.find(i) != frontpath.end()) {
            cur += frontlen[i];
        }else cur += front;
        ans = min(ans,cur);

        swap(a,b);
        cur = dis[0][a] + dis[3][b] + weight[i] + d[i];
        if(backpath.find(i) != backpath.end()) {
            cur += backlen[i];
        } else cur += back;
        ans = min(ans, cur);
        // inverst second pass

        // cur = dis[1][b] + dis[2][a] + weight[i] + d[i];
        // if(frontpath.find(i) != frontpath.end()) {
        //     cur += frontlen[i];
        // }else cur += front;
        // ans = min(ans,cur);
        
        
        */

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