Submission #1267167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267167		cmiuc	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	443 ms	40924 KiB

commuter_pass

#include <iostream>
#include <set>
#include <vector>

using namespace std;
#define int long long
const int N = 2e5 + 10;
int dist[5][N], seen[N], a[N], b[N], c[N], U[N], V[N];
vector<pair<int,int>> nei[N];
vector<int> dag[N], vec;

void dfs(int u){
    seen[u] = 1;
    for (int i : dag[u]){
        if (seen[i] == 0)
            dfs(i);
    }
    // cout<<u<<endl;
    vec.push_back(u);
}

void dijkstra(int s, int id){
    for (int i=1;i<N;i++)
        dist[id][i] = U[i] = V[i] = 1e17;
    dist[id][s] = 0;
    set<pair<int,int>> st = {{0, s}};

    while (st.size() > 0){
        auto [dt, u] = *begin(st);
        st.erase(begin(st));

        for (auto [i, w] : nei[u]){
            if (dist[id][i] > dist[id][u] + w){
                st.erase({dist[id][i], i});
                dist[id][i] = dist[id][u] + w;
                st.insert({dist[id][i], i});
            }
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m, s, t, u, v;
    cin>>n>>m>>s>>t>>u>>v;

    for (int i=1;i<=m;i++){
        cin>>a[i]>>b[i]>>c[i];

        nei[a[i]].push_back({b[i], c[i]});
        nei[b[i]].push_back({a[i], c[i]});
    }

    dijkstra(u, 1);
    dijkstra(v, 2);
    dijkstra(s, 3);
    dijkstra(t, 4);

    for (int i=1;i<=m;i++){
        for (int j : {0, 1}){
            swap(a[i], b[i]);
            if (dist[3][a[i]] + dist[4][b[i]] + c[i] == dist[3][t])
                dag[a[i]].push_back(b[i]);
        }
    }

    for (int i=1;i<=n;i++){
        if (!seen[i])
            dfs(i);
    }
    int Ans = dist[1][v];
    for (int i : vec){
        U[i] = dist[1][i];
        V[i] = dist[2][i];
        for (int j : dag[i]){
            U[i] = min(U[i], U[j]);
            V[i] = min(V[i], V[j]);
        }

        Ans = min(Ans, min(dist[1][i] + V[i], dist[2][i] + U[i]));
    }
    cout<<Ans<<'\n';
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45