Submission #757451

#	Time	Username	Problem	Language	Result	Execution time	Memory
757451		salmon	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	389 ms	26004 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> adjlst[100100];
vector<pair<int,int>> fadj[100100];
vector<pair<int,int>> badj[100100];
int N,M;
int s,t;
int u,v;
int a,b,h;
long long int du[100100],dv[100100],ds[100100],dt[100100];
bool visited[100100];
priority_queue<pair<long long int, int>, vector<pair<long long int, int>>,greater<pair<long long int, int>>> pq;

int main(){
    scanf(" %d",&N);
    scanf(" %d",&M);

    scanf(" %d",&s);
    scanf(" %d",&t);

    scanf(" %d",&u);
    scanf(" %d",&v);

    s--;
    t--;
    u--;
    v--;

    for(int i = 0; i < N; i++){
        du[i] = 1100100100100100100;
        dv[i] = 1100100100100100100;
        ds[i] = 1100100100100100100;
        dt[i] = 1100100100100100100;
        visited[i] = false;
    }

    for(int i = 0; i < M; i++){
        scanf(" %d",&a);
        scanf(" %d",&b);
        scanf(" %d",&h);

        a--;
        b--;

        adjlst[a].push_back(make_pair(b,h));
        adjlst[b].push_back(make_pair(a,h));
    }

    pq.push(make_pair(0,u));
    du[u] = 0;

    while(!pq.empty()){
        int i = pq.top().second;
        long long int d = pq.top().first;
        pq.pop();

        if(!visited[i]){
            visited[i] = true;
            for(pair<int, int> j : adjlst[i]){
                if(d + j.second < du[j.first]){
                    du[j.first] = d + j.second;
                    pq.push(make_pair(d + j.second, j.first));
                }
            }
        }
    }

    for(int i = 0; i < N; i++) visited[i] = false;

    pq.push(make_pair(0,v));
    dv[v] = 0;

    while(!pq.empty()){
        int i = pq.top().second;
        long long int d = pq.top().first;
        pq.pop();

        if(!visited[i]){
            visited[i] = true;
            for(pair<int, int> j : adjlst[i]){
                if(d + j.second < dv[j.first]){
                    dv[j.first] = d + j.second;
                    pq.push(make_pair(d + j.second, j.first));
                }
            }
        }
    }

    for(int i = 0; i < N; i++) visited[i] = false;

    pq.push(make_pair(0,s));
    ds[s] = 0;

    while(!pq.empty()){
        int i = pq.top().second;
        long long int d = pq.top().first;
        pq.pop();

        if(!visited[i]){
            visited[i] = true;
            for(pair<int, int> j : adjlst[i]){
                if(d + j.second < ds[j.first]){
                    ds[j.first] = d + j.second;
                    pq.push(make_pair(d + j.second, j.first));
                }
            }
        }
    }

    for(int i = 0; i < N; i++) visited[i] = false;

    pq.push(make_pair(0,t));
    dt[t] = 0;

    while(!pq.empty()){
        int i = pq.top().second;
        long long int d = pq.top().first;
        pq.pop();

        if(!visited[i]){
            visited[i] = true;
            for(pair<int, int> j : adjlst[i]){
                if(d + j.second < dt[j.first]){
                    dt[j.first] = d + j.second;
                    pq.push(make_pair(d + j.second, j.first));
                }
            }
        }
    }

    long long int STD = dt[s];
    long long int meen[N];
    vector<pair<long long int,  int>> topo;
    for(int i = 0; i < N; i++) topo.emplace_back(ds[i],i);
    for(int i = 0; i < N; i++) meen[i] = 1100100100100100100;

    long long int big = du[v];
    //printf("%lld ",STD);

    sort(topo.begin(),topo.end());

    for(int i = 0; i < topo.size(); i++){
        int j = topo[i].second;

        if(ds[j] + dt[j] > STD) continue;

        meen[j] = min(meen[j],du[j]);
        big = min(big,meen[j] + dv[j]);

        for(pair<int,int> ii : adjlst[j]){
            int k = ii.first;

            if(ii.second + ds[j] + dt[k] == STD) meen[k] = min(meen[k],meen[j]);
        }
    }

    for(int i = 0; i < N; i++) meen[i] = 1100100100100100100;

    reverse(topo.begin(),topo.end());

    for(int i = 0; i < topo.size(); i++){
        int j = topo[i].second;

        if(ds[j] + dt[j] > STD) continue;

        meen[j] = min(meen[j],du[j]);
        big = min(big,meen[j] + dv[j]);

        for(pair<int,int> ii : adjlst[j]){
            int k = ii.first;

            if(ii.second + dt[j] + ds[k] == STD) meen[k] = min(meen[k],meen[j]);
        }
    }

    printf("%lld",big);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int i = 0; i < topo.size(); i++){
      |                    ~~^~~~~~~~~~~~~
commuter_pass.cpp:161:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for(int i = 0; i < topo.size(); i++){
      |                    ~~^~~~~~~~~~~~~
commuter_pass.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
commuter_pass.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
commuter_pass.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf(" %d",&s);
      |     ~~~~~^~~~~~~~~~
commuter_pass.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf(" %d",&t);
      |     ~~~~~^~~~~~~~~~
commuter_pass.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf(" %d",&u);
      |     ~~~~~^~~~~~~~~~
commuter_pass.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf(" %d",&v);
      |     ~~~~~^~~~~~~~~~
commuter_pass.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf(" %d",&a);
      |         ~~~~~^~~~~~~~~~
commuter_pass.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf(" %d",&b);
      |         ~~~~~^~~~~~~~~~
commuter_pass.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf(" %d",&h);
      |         ~~~~~^~~~~~~~~~

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