Submission #1104550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104550		hiensumi	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	213 ms	21840 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]);
}

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:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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