Submission #899998

#	Time	Username	Problem	Language	Result	Execution time	Memory
899998		lalig777	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	2058 ms	28676 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, minUdist, minVdist;

void resolver (int nodo){
    ll save1=minUdist, save2=minVdist;
    for (int i=0; i<padre[nodo].size(); i++){
        int pad=padre[nodo][i];
        if (minUdist>Udist[pad]) minUdist=Udist[pad];
        if (minVdist>Vdist[pad]) minVdist=Vdist[pad];
        ans=min(ans, minUdist+minVdist);
        resolver(pad);
        minUdist=save1;
        minVdist=save2;
    }
    return;
}


int main(){
    int N, M, S, T, U, V;
    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);
        }
    }
    ans=Udist[V];
    minUdist=Udist[T];
    minVdist=Vdist[T];
    ans=min(ans, minUdist+minVdist);
    resolver(T);
    cout<<ans<<endl; 
    

    return 0;
}

Compilation message (stderr)

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

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