Submission #884522

#	Time	Username	Problem	Language	Result	Execution time	Memory
884522		mohammadsam	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	284 ms	31464 KiB

commuter_pass

/*
    in the name of god
    created by: mohammadsam
*/
 
#include <bits/stdc++.h>
 
using namespace std;
#define int long long 
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;
 
#define min_heap(X)   priority_queue<X,vector<X>,greater<X>>
#define max_heap(X)   priority_queue<X>
#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define loop(i,f,d)   for(int i = f;i<d;i++)
#define loop2(j,f,d)  for(int j = f;j>=d;j--)
#define len(V)        V.size()
#define sep           ' '
#define endl          '\n'
#define pb(x)         push_back(x)
#define debug(x)      cerr  << "bug " << x << endl;
#define migmig        cin.tie(NULL);ios_base::sync_with_stdio(false);
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define md(x)         (((x%MD)+MD)%MD)
#define all(V)        V.begin(),V.end()
#define Mp(a,b)       make_pair(a,b)
#define gaws(a,b)     (((b-a+1LL)*(a+b))/2LL)
#define vvi           vector<vector<int>>
#define setprec(x)    fixed << setprecision(x)
 
const ll N = 2e5 + 100, MD = 1e9 + 7;
const ll inf = 1e17 , riz = -2e9;
int n , m , s, t , u ,v;
vector<pii> g[N];
int dis2[2][N],dp[2][2][N],dis[2][N];
min_heap(pii) pq;
int ans = inf;
void dij(int u,int p){
    fill(dis2[p],dis2[p]+n+1,inf);
    dis2[p][u] = 0;
    pq.push(Mp(0,u));
    while(!pq.empty()){
        auto [d,u] = pq.top();pq.pop();
        if(d!=dis2[p][u]) continue;
        for(auto [h,w] : g[u]){
            if(dis2[p][h] > dis2[p][u] + w){
                dis2[p][h] = dis2[p][u] + w;
                pq.push(Mp(dis2[p][h],h));
            }
        }
    }
}
void dij2(int u,int ind,int p){
    fill(dis[ind],dis[ind]+n+1,inf);
    loop(i,1,n+1) dp[ind][p][i] = dis2[p][i]; 
    dis[ind][u] = 0 ;
    pq.push(Mp(0,u));
    while(!pq.empty()){
        auto [d,u] = pq.top();pq.pop();
        if(dis[ind][u] != d) continue;
        for(auto [h,w] : g[u]){
            if(dis[ind][h] > dis[ind][u] + w){
                dis[ind][h] = dis[ind][u] + w;
                dp[ind][p][h] = min(dp[ind][p][h],dp[ind][p][u]);
                pq.push(Mp(dis[ind][h],h));
            }
        }
    }
}
int32_t main() {
    migmig
    cin >> n >> m >> s >> t >> u >> v;
    loop(i,0,m){
        int a,b,w;
        cin >> a >> b >> w;
        g[a].pb(Mp(b,w));
        g[b].pb(Mp(a,w));
    }
    dij(u,0);
    dij(v,1);
    dij2(s,0,0);
    dij2(t,1,0);
    dij2(s,0,1);
    dij2(t,1,1);
    //cout<<"---" << endl;
    //cout << dp[0][1] << endl;
    loop(i,1,n+1){
        if(dis[0][i] + dis[1][i] == dis[0][t]){
            ans = min(ans,dis2[0][i]+min(dp[0][1][i],dp[1][1][i]));
            ans = min(ans,dis2[1][i]+min(dp[0][0][i],dp[1][0][i]));
            //cout << i << sep << ans << sep << dis2[1][i] << sep << dp[0][i] << endl;
        }
    }
    cout << min(ans,dis2[0][v]) << endl;
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dij(long long int, long long int)':
commuter_pass.cpp:47:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |         auto [d,u] = pq.top();pq.pop();
      |              ^
commuter_pass.cpp:49:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |         for(auto [h,w] : g[u]){
      |                  ^
commuter_pass.cpp: In function 'void dij2(long long int, long long int, long long int)':
commuter_pass.cpp:63:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |         auto [d,u] = pq.top();pq.pop();
      |              ^
commuter_pass.cpp:65:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |         for(auto [h,w] : g[u]){
      |                  ^

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