Submission #1106102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106102		hiensumi	Commuter Pass (JOI18_commuter_pass)	C++14	31 / 100	166 ms	22084 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define fod(i,a,b) for(int i((int) (a)), _b(b); i <= _b; i++)
#define fok(i,a,b) for(int i((int) (a)), _b(b); i >= _b; i--)
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ve vector
#define vi ve<int>
#define vll ve<ll>
#define el '\n'
#define mask(i) (1LL<<(i))
#define BIT(msk,i) (msk>>(i)&1LL)
template<class T> bool mini(T &a, T b){ return (a > (b) ? a = (b), 1 : 0); }
template<class T> bool maxi(T &a, T b){ return (a < (b) ? a = (b), 1 : 0); }
const int base = mask(20) + 5;
#define name "commuter_pass"
 
const int N = 1e5;
 
int n, m;
 
int S, T;
int U, V;
 
ll res;
 
ve <ve<pii>> g;
 
ll dis_s[N + 5];
ll dis_u[N + 5];
ll dis_v[N + 5];
 
inline void djikstra(int s, ll *dis){
    fod(i,1,n) dis[i] = 1e18;
    dis[s] = 0;
 
    priority_queue <pair<ll,int>> pq;
 
    pq.push(mp(0, s));
 
    while(!pq.empty()){
        ll val;
        int u;
        tie(val, u) = pq.top(); pq.pop();
 
        if(-val != dis[u]) continue;
 
        for(pii who : g[u]){
            int v, w; tie(v, w) = who;
 
            if(mini(dis[v], dis[u] + w)){
                pq.push(mp(-dis[v], v));
            }
        }
    }
}
 
ll dp_u[N + 5];
ll dp_v[N + 5];
 
bool vst[N + 5];
 
void dfs(int x){
    dp_u[x] = dis_u[x];
    dp_v[x] = dis_v[x];
 
    vst[x] = 1;
 
    for(pii who : g[x]){
        int y, w; tie(y, w) = who;
 
        if(dis_s[x] == dis_s[y] + w){
            if(!vst[y]) dfs(y);
 
            mini(dp_u[x], dp_u[y]);
            mini(dp_v[x], dp_v[y]);
        }
    }
 
    mini(res, dp_u[x] + dis_v[x]);
    mini(res, dp_v[x] + dis_u[x]);
 	mini(res, dp_u[x] + dp_v[x]);
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    if(fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
 
    cin >> n >> m;
 
    cin >> S >> T;
    cin >> U >> V;
 
    g.resize(n + 1);
    fod(i,1,m){
        int u, v, w; cin >> u >> v >> w;
        g[u].pb(mp(v, w));
        g[v].pb(mp(u, w));
    }
 
    djikstra(S, dis_s);
    djikstra(U, dis_u);
    djikstra(V, dis_v);
 
    res = dis_u[V];
 
    dfs(T);
 
    cout << res;
 
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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