Submission #851650

#	Time	Username	Problem	Language	Result	Execution time	Memory
851650		_Nhm207_	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	206 ms	51144 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;

#define        RUN_FAST    ios_base::sync_with_stdio(false);cin.tie(0) ;cout.tie(0);

#define     HEAP_MIN(x)    priority_queue<x,vector<x>,greater<x>>
#define     HEAP_MAX(x)    priority_queue<x>

#define refo(i , a , b)    for(int i = a ; i >= b ; i--)
#define  rep(i , a , b)    for(int i = a ; i < b ; i++)
#define   fo(i , a , b)    for(int i = a ; i <= b ; i++)
#define      fov(x , y)    for(auto x : y)
#define          bpc(x)    __builtin_popcount(x)

#define              ii     pair<int,int>
#define             iii     pair<int,ii>
#define              iv     pair<ii,ii>

#define              ll    long long
#define             int    long long
#define            endl    "\n"

#define             psb    push_back
#define             psf    push_front
#define             pof    pop_front()
#define             pob    pop_back()
#define             ins    insert
#define              fi    first
#define              se    second
#define              fr    front()
#define              bk    back()
#define             sz()    size()

const int N = 1e6 + 5;
const int K = 105;
const int mod = 1e9 + 7;
const ll inf = 1e18;
const double esp = 1e-6;
const bool MoreThanOneTest = 0;

int query  , gt[N] ;

int dx[] = { 1 , -1 , 0 , 0 };

int dy[] = { 0 , 0 , -1 , 1 };

int bit(int i , int k){
    return ( i >> k ) & 1;
}

int off(int i , int k){
    return i ^ ( 1 << k );
}

int Pow(int n , int k){
    if(k == 0) return 1;
    int t = Pow(n , k / 2) % mod;
    if(k % 2) return  t * t % mod * n % mod;
    else return t % mod * t % mod;
}

void TinhGiaiThua(){
    gt[0] = 1;
    fo(i , 1 , N - 5) gt[i] = (gt[i - 1] % mod * i % mod )% mod;
    return ;
}

int C(int n , int k){
    k = gt[k] % mod * gt[n - k] % mod % mod;
    n = gt[n] % mod;
    return n % mod * Pow(k , mod - 2) % mod;
}

// ( a % mod ) / ( b % mod ) = a % mod * b ^ ( mod - 2) % mod
// a ^ b % mod = a % mod ^ (b % (mod - 1))

//    author : Nhm207

//                     DECLARE
//__________________________________________________________

int n , m , u , v , uu , vv , c , s , t , ds[N] , dt[N] , du[N] , dv[N];

vector<ii> g[N];

bool ok[N];

bool in_path[N];

HEAP_MIN(ii) heap;

//__________________________________________________________

void PreBuild(){
    cin >> n >> m;
    cin >> s >> t;
    cin >> uu >> vv;
    fo(i , 1 , m){
        cin >> u >> v >> c;
        g[u] . psb({v , c});
        g[v] . psb({u , c});
    }
    return;
}
void dijks(){
    fo(i , 1 , n) ds[i] = inf;
    ds[s] = 0;
    heap . push({0 , s});
    while(heap . sz()){
        ii cur = heap . top();
        heap . pop();
        int u = cur . se;
        fov(tmp , g[u]){
            int c = tmp . se;
            int v = tmp . fi;
            if(ds[v] > ds[u] + c){
                ds[v] = ds[u] + c;
                heap . push({ds[v] , v});
            }
        }
    }
}
void dijkt(){
    fo(i , 1 , n) dt[i] = inf;
    dt[t] = 0;
    heap . push({0 , t});
    while(heap . sz()){
        ii cur = heap . top();
        heap . pop();
        int u = cur . se;
        fov(tmp , g[u]){
            int c = tmp . se;
            int v = tmp . fi;
            if(dt[v] > dt[u] + c){
                dt[v] = dt[u] + c;
                heap . push({dt[v] , v});
            }
        }
    }
}
void dijku(){
    fo(i , 1 , n) du[i] = inf;
    du[uu] = 0;
    heap . push({0 , uu});
    while(heap . sz()){
        ii cur = heap . top();
        heap . pop();
        int u = cur . se;
        fov(tmp , g[u]){
            int c = tmp . se;
            int v = tmp . fi;
            if(du[v] > du[u] + c){
                du[v] = du[u] + c;
                heap . push({du[v] , v});
            }
        }
    }
}
void dijkv(){
    fo(i , 1 , n) dv[i] = inf;
    dv[vv] = 0;
    heap . push({0 , vv});
    while(heap . sz()){
        ii cur = heap . top();
        heap . pop();
        int u = cur . se;
        fov(tmp , g[u]){
            int c = tmp . se;
            int v = tmp . fi;
            if(dv[v] > dv[u] + c){
                dv[v] = dv[u] + c;
                heap . push({dv[v] , v});
            }
        }
    }
}
void _Nhm207_(){
    dijks();
    dijkt();
    dijku();
    dijkv();
    memset(in_path , false , sizeof(in_path));
    fo(i , 1 , n) if(ds[i] + dt[i] == ds[t]) in_path[i] = true;
    int ans = inf;
    fo(i , 1 , n){
        if(in_path[i]){
            ans = min(ans , (in_path[uu] ? 0 : du[i]) + (in_path[vv] ? 0 : dv[i]));
        }
    }
    cout << min(ans , du[v]);



    return;
}

int32_t main()
{
    RUN_FAST
    //freopen("      .inp","r",stdin);
    //freopen("      .out","w",stdout);
    PreBuild();
    if( MoreThanOneTest ){
        cin >> query;
        while( query-- ){
            _Nhm207_();
        }
    }
    else _Nhm207_();
}

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