Submission #884520

#	Time	Username	Problem	Language	Result	Execution time	Memory
884520		mohammadsam	Commuter Pass (JOI18_commuter_pass)	C++14	24 / 100	36 ms	7980 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 = 1000, MD = 1e9 + 7;
const ll inf = 1e17 , riz = -2e9;
int n , m , s, t , u ,v;
vector<pii> g[N];
int dis[N][N];
min_heap(pii) pq;
int ans = inf;
void dij(int u,int p){
    fill(dis[p],dis[p]+n+1,inf);
    dis[p][u] = 0;
    pq.push(Mp(0,u));
    while(!pq.empty()){
        auto [d,u] = pq.top();pq.pop();
        if(d!=dis[p][u]) continue;
        for(auto [h,w] : g[u]){
            if(dis[p][h] > dis[p][u] + w){
                dis[p][h] = dis[p][u] + w;
                pq.push(Mp(dis[p][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));
    }
    loop(i,1,n+1) dij(i,i);
    int ans = dis[u][v];
    loop(i,1,n+1){
        loop(j,1,n+1){
            if(dis[s][i] + dis[i][j] + dis[j][t] == dis[s][t]){
                ans = min(ans,dis[u][i]+dis[v][j]);
                ans = min(ans,dis[v][i]+dis[u][j]);
            } 
        }
    }
    cout << ans << 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]){
      |                  ^

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