Submission #397085

#	Time	Username	Problem	Language	Result	Execution time	Memory
397085		giorgikob	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	393 ms	41948 KiB

commuter_pass

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 1e6+50, mod = 1e9+7, K = 31;

int n,m;
int S,T,U,V;
int x,y,w;
vector<pair<int,int>>gr[N];
ll D[5][N];
int A[5],ind[5];
ll dp[5][N];

inline void dijkstra(int x){

    priority_queue<pair<ll,int>>q;
    vector<int>fix(n+5,0);

    int a = ind[x];

    for(int i = 1; i <= n; i++){
        D[a][i] = 1e18;
    }

    D[a][x] = 0;
    q.push({0,x});
    while(q.size()){
        auto p = q.top();
        q.pop();
        int x = p.ss;
        ll dist = -p.ff;
        if(fix[x]) continue;
        fix[x] = 1;

        //cout << x << " " ;

        for(auto pp : gr[x]){
            int to = pp.ff;
            ll w = pp.ss;
            ll new_dist = dist + w;
            if(D[a][to] > new_dist){
                D[a][to] = new_dist;
                q.push({-new_dist,to});
            }
        }
    }
}

ll dist_st;

inline bool on_pass(int x){
    return dist_st == (D[ind[S]][x] + D[ind[T]][x]);
}

inline void bfs(int X){

    vector<pair<ll,int>>v;
    for(int i = 1; i <= n; i++){
        if(on_pass(i)){
            v.pb({D[ind[X]][i],i});
        }
    }

    int a = ind[X];
    sort(v.begin(),v.end());
    for(int i = 0; i < v.size(); i++){
        int x = v[i].ss;
        //cout << x << endl;
        dp[a][x] = min(dp[a][x],D[ind[U]][x]);
        for(auto pp : gr[x]){
            int to = pp.ff;
            dp[a][x] = min(dp[a][x],dp[a][to]);
        }
    }
}

inline void test_case(){
    cin >> n >> m;
    for(int i = 1; i <= 4; i++){
        cin >> A[i];
        ind[A[i]] = i;
    }
    S = A[1]; T = A[2]; U = A[3]; V = A[4];

    for(int i = 1; i <= m; i++){
        cin >> x  >> y >> w;
        gr[x].pb({y,w});
        gr[y].pb({x,w});
    }

    for(int i = 1; i <= 4; i++) dijkstra(A[i]);

    dist_st = D[ind[S]][T];

    for(int i = 1; i <= n; i++) dp[ind[S]][i] = dp[ind[T]][i] = 1e18;

    bfs(S);
    bfs(T);

    ll answer = D[ind[U]][V];
    for(int i = 1; i <= n; i++){
        //cout << i << " " << dp[ind[S]][i] << " " << dp[ind[T]][i] << endl;
        answer = min(answer, min(dp[ind[S]][i], dp[ind[T]][i]) + D[ind[V]][i]);
    }

    cout << answer << endl;
}
 main(){
    ios::sync_with_stdio(0);

    int T = 1;
    //cin >> T;
    for(int i = 1; i <= T; i++){
        test_case();
    }
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void bfs(int)':
commuter_pass.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int>, std::allocator<std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:112:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 |  main(){
      |       ^

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