Submission #854374

#	Time	Username	Problem	Language	Result	Execution time	Memory
854374		Zero_OP	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	212 ms	21344 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;

template<class T> bool minimize(T& a, T b){
    if(a>b) return a=b, true;
    return false;
}

template<class T> bool maximize(T& a, T b){
    if(a<b) return a=b, true;
    return false;
}

#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))

typedef long long ll;
typedef unsigned long long ull;

const int N=1e5+5;

int n, m;
vector<pair<int, int>> g[N];
vector<int> par[N];

vector<ll> dijkstra(int st){
    priority_queue<pair<ll, int>> pq;
    vector<ll> d(n, -1); d[st]=0;

    pq.push({0, st});
    while(!pq.empty()){
        ll cost; int u;
        tie(cost, u)=pq.top(); pq.pop();

        if(-cost!=d[u]) continue;

        for(int i=0; i<g[u].size(); ++i){
            int v, w; tie(v, w)=g[u][i];
            if(d[v]==-1 or (d[v]>(d[u]+w))){
                d[v]=d[u]+w;
                pq.push({-d[v], v});
            }
        }
    }

    return d;
}

vector<ll> dijkstra_withTrace(int st){
    vector<ll> d(n, -1); d[st]=0;
    priority_queue<pair<ll, int>> pq;
    pq.push({0, st});

    while(!pq.empty()){
        ll cost; int u;
        tie(cost, u)=pq.top(); pq.pop();

        if(-cost!=d[u]) continue;

        for(int i=0; i<g[u].size(); ++i){
            int v, w; tie(v, w)=g[u][i];
            if(d[v]==-1 or (d[v]>d[u]+w)){
                d[v]=d[u]+w;
                par[v].clear(); par[v].push_back(u);
                pq.push({-d[v], v});
            }
            else if(d[v]==d[u]+w) par[v].push_back(u);
        }
    }

    return d;
}

void Zero_OP(){
    int s, t, U, V; cin>>n>>m>>s>>t>>U>>V;
    --s, --t, --U, --V;
    while(m--){
        int a, b, c; cin>>a>>b>>c;
        --a, --b;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    vector<ll> dU=dijkstra(U), dV=dijkstra(V), dS=dijkstra_withTrace(s);

    ll ans=dU[V];

    priority_queue<pair<ll, int>> pq;
    vector<ll> d(n, -1); d[t]=dV[t];

    pq.push({-d[t], t});

    while(!pq.empty()){
        ll cost; int u;
        tie(cost, u)=pq.top();  pq.pop();
        if(-cost!=d[u]) continue;

        minimize(ans, d[u]+dU[u]);

        for(int i=0; i<par[u].size(); ++i){
            int v=par[u][i];
            if(d[v]==-1 or (d[v]>min(d[u], dV[v]))){
                d[v]=min(d[u], dV[v]);
                pq.push({-d[v], v});
            }
        }
    }

    fill(range(d), -1); d[t]=dU[t];
    pq.push({-d[t], t});
    while(!pq.empty()){
        ll cost; int u;
        tie(cost, u)=pq.top(); pq.pop();

        if(-cost!=d[u]) continue;

        minimize(ans, d[u]+dV[u]);
        for(int i=0; i<par[u].size(); ++i){
            int v=par[u][i];
            if(d[v]==-1 or (d[v]>min(d[u], dU[v]))){
                d[v]=min(d[u], dU[v]);
                pq.push({-d[v], v});
            }
        }
    }

    cout<<ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    Zero_OP();

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'std::vector<long long int> dijkstra(int)':
commuter_pass.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int i=0; i<g[u].size(); ++i){
      |                      ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'std::vector<long long int> dijkstra_withTrace(int)':
commuter_pass.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int i=0; i<g[u].size(); ++i){
      |                      ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void Zero_OP()':
commuter_pass.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(int i=0; i<par[u].size(); ++i){
      |                      ~^~~~~~~~~~~~~~
commuter_pass.cpp:119:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int i=0; i<par[u].size(); ++i){
      |                      ~^~~~~~~~~~~~~~

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