Submission #836143

#	Time	Username	Problem	Language	Result	Execution time	Memory
836143		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	325 ms	35912 KiB

commuter_pass

/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second

const int N = 1e5 + 5;
long long int n, m, s, t, u, v;
long long int a, b, c;
vector<pair<long long int, long long int>> edge[N];
long long int du[N], dus[N];
long long int dv[N], dvs[N];
long long int ds[N];
vector<long long int> par[N];
bool visited[N];

long long int pathU(long long int cur){
    if(visited[cur]){
        return dus[cur];
    }
    visited[cur] = true;
    for(int i = 0; i < par[cur].size(); i++){
        dus[cur] = min(dus[cur], pathU(par[cur][i]));
    }
    return dus[cur];
}

long long int pathV(long long int cur){
    if(visited[cur]){
        return dvs[cur];
    }
    visited[cur] = true;
    for(int i = 0;  i < par[cur].size(); i++){
        dvs[cur] = min(dvs[cur], pathV(par[cur][i]));
    }
    return dvs[cur];
}


void solve(){
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        edge[a].push_back({b, c});
        edge[b].push_back({a, c});
    }
    for(int i = 0; i < N; i++){
        du[i] = dv[i] = ds[i] = 1e9*(n + 1);
    }
    
    priority_queue<pair<long long int, long long int>,  vector<pair<long long int, long long int>>, greater<pair<long long int, long long int>>> pq;
    //djikstra dari u
    pq.push({0, u});
    while(!pq.empty()){
        long long int cst = pq.top().fi, cur = pq.top().se;
        pq.pop();
        if(du[cur] > cst){
            du[cur] = cst;
            for(int i = 0; i < edge[cur].size(); i++){
                pq.push({edge[cur][i].se + cst,  edge[cur][i].fi});
            }
        }
    }
    
    //djikstra dari v
    pq.push({0, v});
    while(!pq.empty()){
        long long int cst = pq.top().fi, cur = pq.top().se;
        pq.pop();
        if(dv[cur] > cst){
            dv[cur] = cst;
            for(int i = 0; i < edge[cur].size(); i++){
                pq.push({edge[cur][i].se + cst, edge[cur][i].fi});
            }
        }
    }
    
    //cari shortest path
    vector<long long int> parTem[N];
    pq.push({0, s});
    while(!pq.empty()){
        long long int cur = pq.top().se, cst = pq.top().fi;
        pq.pop();
        if(cur == t){
            break;
        }
        if(ds[cur] >= cst){
            ds[cur] = cst;
            for(int i = 0; i < edge[cur].size(); i++){
                if(ds[edge[cur][i].fi] > cst + edge[cur][i].se){
                    ds[edge[cur][i].fi] = cst + edge[cur][i].se;
                    parTem[edge[cur][i].fi].clear();
                    parTem[edge[cur][i].fi].push_back(cur);
                    pq.push({cst + edge[cur][i].se, edge[cur][i].fi});
                }else if(ds[edge[cur][i].fi] == cst + edge[cur][i].se){
                    parTem[edge[cur][i].fi].push_back(cur);
                }
            }
        }
    }
    memset(visited, 0, sizeof(visited));
    queue<long long int> qi;
    qi.push(t);
    while(!qi.empty()){
        long long int k = qi.front();
        qi.pop();
        if(!visited[k]){
            visited[k] = true;
            par[k] = parTem[k];
            for(int i = 0; i < par[k].size(); i++){
                qi.push(par[k][i]);
            }
        }
    }
    for(int i = 0; i <= n; i++){
        dus[i] = du[i];
        dvs[i] = dv[i];
    }
    memset(visited, 0, sizeof(visited));
    pathU(t);
    memset(visited, 0, sizeof(visited));
    pathV(t);
    long long int res = 1e16;
    for(int i = 1; i <= n; i++){
        res = min(res, dus[i] + dv[i]);
        res = min(res, du[i] + dvs[i]);
        
    }
    cout << res << endl;
    
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    while(t--){
        solve();
    }

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'long long int pathU(long long int)':
commuter_pass.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 0; i < par[cur].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'long long int pathV(long long int)':
commuter_pass.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0;  i < par[cur].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:70:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for(int i = 0; i < edge[cur].size(); i++){
      |                            ~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:83:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for(int i = 0; i < edge[cur].size(); i++){
      |                            ~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:100:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for(int i = 0; i < edge[cur].size(); i++){
      |                            ~~^~~~~~~~~~~~~~~~~~
commuter_pass.cpp:121:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             for(int i = 0; i < par[k].size(); i++){
      |                            ~~^~~~~~~~~~~~~~~

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