Submission #788553

#	Time	Username	Problem	Language	Result	Execution time	Memory
788553		prefixorsuuffiixx	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	398 ms	27852 KiB

commuter_pass

//ashoori is my love
//ashoori is my love//ashoori is my love//ashoori is my love//ashoori is my love//ashoori is my love
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef int it;
typedef pair<ll, ll> pii;
typedef pair<ll, pii> piii;
#pragma GCC optimize ("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops,Ofast")
#define sep  "\n"
#define pes  " "
#define int long long
#define print(x,n) for(int i=1; i<=n ; i++)cout<<x[i]<<" "
#define scan(x,n) for(int i=1 ; i<=n ; i++)cin>>x[i]
#define all(x) x.begin(), x.end()
#define pb push_back
#define F first
#define Se second
#define sz size
#define cin2(r,j) cin>>r>>j
#define cin1(r) cin>>r
#define cin3(r,j,k) cin>>r>>j>>k
# define InTheNameOfGod                                  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxx=1e5+1000;
const ll MOD=1000000007;
const ll inf=1e18;


int S,T,U,V,n,m;
vector<pii> g[maxx];
vector<ll> distances[maxx];

void dij(int v , int T)
{

    vector<ll> ashoori(maxx-10);
    for(int i =  1 ; i <= n+10 ; i++)ashoori[i] = inf;
     priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
     ashoori[v]=0;
    pq.push({0,v});
    while(!pq.empty()){
        int node = pq.top().Se;
        int ce = pq.top().F;
        pq.pop();
        //if(ce!=ashoori[node])continue;

        for(auto U : g[node]){


            if(ashoori[node] + U.Se < ashoori[U.F]){
                ashoori[U.F] = ashoori[node] + U.Se;
                pq.push({ashoori[U.F],U.F});
            }
        }

    }


    for(int i = 0 ; i <= n ; i++){
        distances[T].pb(ashoori[i]);

    }


}

bool comp(int a,int b){
    return distances[S][a]<distances[S][b];
}
void solve(){

    cin>>n>>m>>S>>T>>U>>V;
    for(int i = 1 ; i <= m ; i++){
        int u , v , c;
        cin>>u>>v>>c;
        g[u].pb({v,c});
        g[v].pb({u,c});
    }

    dij(T , T);

    dij(S , S);

    dij(U , U );

    dij(V , V);

    /*for(auto J : distances[V])cout<<J<<" ";
    cout<<"\n";*/
    int answer = distances[U][V];
    int mn[maxx];
    for(int i = 0 ; i < maxx ; i++)mn[i] = inf;
    vector<int> nodes;
    for(int i = 1 ; i <= n ; i++){
        if(distances[S][i] + distances[T][i] == distances[S][T])nodes.pb(i);
    }
    sort(all(nodes),comp);

    for(int i = 0 ; i < nodes.sz() ; i ++){
        mn[nodes[i]] = distances[U][nodes[i]];
        for(auto K : g[nodes[i]]){
            mn[nodes[i]] = min(mn[nodes[i]] , mn[K.F]);
        }
        answer = min(mn[nodes[i]] + distances[V][nodes[i]],answer);

    }
    for(int i = 0 ; i < maxx ; i++)mn[i] = inf;

    for(int i = 0 ; i < nodes.sz() ; i ++){
        mn[nodes[i]] = distances[V][nodes[i]];
        for(auto K : g[nodes[i]]){
            mn[nodes[i]] = min(mn[nodes[i]] , mn[K.F]);
        }
        answer = min(mn[nodes[i]] + distances[U][nodes[i]],answer);

    }
    cout<<answer;
}




/*===========================================================================================================================*/
signed main(){
    //InTheNameOfGod;
    //int tt = clock();
    //cout << fixed << setprecision(6);

    int tc = 1;
    //cin>>tc;

    //for(int i = 1 ; i <= 3 ; i++)cout<<dp[i]<<" ";
    while(tc--){solve();

        //cerr << "TIME = " << clock() - tt << endl;
        //tt = clock();
        }


}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dij(long long int, long long int)':
commuter_pass.cpp:46:13: warning: unused variable 'ce' [-Wunused-variable]
   46 |         int ce = pq.top().F;
      |             ^~
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:102:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 0 ; i < nodes.sz() ; i ++){
      |                     ~~^~~~~~~~~~~~
commuter_pass.cpp:112:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i = 0 ; i < nodes.sz() ; i ++){
      |                     ~~^~~~~~~~~~~~

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