Submission #900031

#	Time	Username	Problem	Language	Result	Execution time	Memory
900031		lalig777	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	357 ms	30420 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long ll;

vector<vector<pair<int,ll> > >listaAdy;
priority_queue<pair<ll,int> >pq;
vector<ll>Udist, Vdist, distancia;
vector<vector<int> >padre;
ll ans;
int N, M, S, T, U, V;
vector<pair<ll,ll> >mindist;
vector<bool>visitado;

void resolver (int nodo){
    visitado[nodo]=true;
    mindist[nodo].first=Udist[nodo];
    mindist[nodo].second=Vdist[nodo];
    for (int i=0; i<padre[nodo].size(); i++){
        int pad=padre[nodo][i];
        if (visitado[pad]==false) resolver(pad);
        ll x=min(Udist[nodo], mindist[pad].first);
        ll y=min(Vdist[nodo], mindist[pad].second);
        if (mindist[nodo].first+mindist[nodo].second>x+y){
            mindist[nodo].first=x;
            mindist[nodo].second=y;
        }
    }
    return;
}


int main(){
    cin>>N>>M;
    cin>>S>>T;
    cin>>U>>V;
    S--; T--; U--; V--;
    listaAdy.resize(N);
    while (M--){
        int u, v;
        ll c;
        cin>>u>>v>>c;
        u--; v--;
        listaAdy[u].push_back(make_pair(v, c));
        listaAdy[v].push_back(make_pair(u, c));
    }
    Udist.assign(N, 1e18);
    Vdist.assign(N, 1e18);
    distancia.assign(N, 1e18);
    Udist[U]=0;
    Vdist[V]=0;
    distancia[S]=0;
    //Distancia más corta de U al resto de nodos.
    pq.push(make_pair(0, U));
    while (!pq.empty()){
        ll d=-pq.top().first;
        int u=pq.top().second;
        pq.pop();
        if (Udist[u]<d) continue;
        for (auto vec: listaAdy[u]){
            int v=vec.first;
            ll c=vec.second;
            if (Udist[v]>Udist[u]+c){
                Udist[v]=Udist[u]+c;
                pq.push(make_pair(-Udist[v], v));
            }
        }
    }
    //Distancia más corta de V al resto de nodos.
    pq.push(make_pair(0, V));
    while (!pq.empty()){
        ll d=-pq.top().first;
        int u=pq.top().second;
        pq.pop();
        if (Vdist[u]<d) continue;
        for (auto vec: listaAdy[u]){
            int v=vec.first;
            ll c=vec.second;
            if (Vdist[v]>Vdist[u]+c){
                Vdist[v]=Vdist[u]+c;
                pq.push(make_pair(-Vdist[v], v));
            }
        }
    }
    //Camino más corto entre S i T guardando todos los caminos.
    padre.resize(N);
    pq.push(make_pair(0, S));
    while (!pq.empty()){
        ll d=-pq.top().first;
        int u=pq.top().second;
        pq.pop();
        if (distancia[u]<d) continue;
        for (auto vec: listaAdy[u]){
            int v=vec.first;
            ll c=vec.second;
            if (distancia[v]>distancia[u]+c){
                distancia[v]=distancia[u]+c;
                padre[v].clear();
                padre[v].push_back(u);
                pq.push(make_pair(-distancia[v], v));
            }else if (distancia[v]==distancia[u]+c) padre[v].push_back(u);
        }
    }
    mindist.assign(N, make_pair(1e18, 1e18));
    visitado.assign(N, false);
    ans=Udist[V];
    resolver(T);
    ans=min(ans, mindist[T].first+mindist[T].second);
    cout<<ans<<endl; 
    

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void resolver(int)':
commuter_pass.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i=0; i<padre[nodo].size(); i++){
      |                   ~^~~~~~~~~~~~~~~~~~~

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