Submission #1187550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187550		sergiomoncadamc	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	203 ms	27384 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ld = long double;
#define pb push_back
#define sz size()
typedef pair<int, ll> pil;

const int maxn = 1e5 + 1;
const ll inf = 1e15;
vector<vector<pil>> graph(maxn);
vector<vector<int>> aux(maxn);
vector<int> inDegree(maxn);

struct comp{
    bool operator() (pil a, pil b){
        return a.second > b.second;
    }
};

struct edge {
    int u, v; ll w;

    // Ordenar las aristas por el menor peso
    bool operator<(const edge& that) const {
        return w < that.w; // Cambiar '<' por '>' para hallar el Maximal Spanning Tree
    }
};

// Complejidad O(m*log(n))
void dijkstra(int source, int n, vector<ll>& d, vector<int>& parent){
    for(int i = 1; i <= n; i++){
        d[i] = inf;
        parent[i] = -1;
    }   
    d[source] = 0;
    priority_queue<pil, vector<pil>, comp> pq;
    pq.push({source, 0});
    while(!pq.empty()){
        int u = pq.top().first; ll w1 = pq.top().second;
        pq.pop();
        if(d[u] < w1) continue;
        for(pil edge : graph[u]){
            int v = edge.first; ll w2 = edge.second;
            if(d[v] > w1 + w2){
                d[v] = w1 + w2;
                parent[v] = u;
                pq.push({v, d[v]});
            }
        }
    }
}

void topoSort(int s, vector<int>& orden){
    queue<int> q; q.push(s);
    orden.pb(s);

    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v : aux[u]){
            inDegree[v]--;
            if(!inDegree[v]){
                q.push(v);
                orden.pb(v);
            }
        }
    }
}

void createAuxGraph(int s, int t, vector<ll>& ds, vector<ll>& dt, vector<edge>& edges, vector<bool>& vertexes){
    for(edge e : edges){
        int u = e.u, v = e.v; ll w = e.w;
        if(ds[u] + w + dt[v] == ds[t]){
            aux[u].pb(v);
            inDegree[v]++;
            vertexes[u] = 1; vertexes[v] = 1;
        }

        else if(ds[v] + w + dt[u] == ds[t]){
            aux[v].pb(u);
            inDegree[u]++;
            vertexes[u] = 1; vertexes[v] = 1;
        }
    }
}

void solver(){
    int n, m, s, t, u, v; cin>>n>>m>>s>>t>>u>>v;
    vector<edge> edges;
    for(int i = 0; i < m; i++){
        int a, b; ll w;
        cin>>a>>b>>w;
        edges.pb({a, b, w});
        graph[a].pb({b, w});
        graph[b].pb({a, w});
    }
    vector<ll> ds(n+1), dt(n+1), du(n+1), dv(n+1);
    vector<int> parentS(n+1), parentT(n+1), parentU(n+1), parentV(n+1);
    dijkstra(s, n, ds, parentS);
    dijkstra(t, n, dt, parentT);
    dijkstra(u, n, du, parentU);
    dijkstra(v, n, dv, parentV);
    vector<bool> vertexes(n+1);
    createAuxGraph(s, t, ds, dt, edges, vertexes);
    vector<int> orden;
    topoSort(s, orden);

    vector<ll> dpU(n+1, inf);
    for(int i = 0; i < orden.sz; i++){
        int a = orden[i];

        dpU[a] = du[a];
        if(parentS[a] != -1 && vertexes[parentS[a]]) dpU[a] = min(dpU[a], dpU[parentS[a]]);
    }

    vector<ll> dpV(n+1, inf);
    for(int i = 0; i < orden.sz; i++){
        int a = orden[i];

        dpV[a] = dv[a];
        if(parentS[a] != -1 && vertexes[parentS[a]]) dpV[a] = min(dpV[a], dpV[parentS[a]]);
    }

    ll ans = du[v];
    for(int i = 0; i < orden.sz; i++) ans = min(ans, dpU[orden[i]] + dpV[orden[i]]);
    cout<<ans<<endl;
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    int t = 1;
    // cin>>t;
    while(t--){
        solver();
    }

    return 0;
}

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