Submission #1224129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224129		Bui_Quoc_Cuong	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	163 ms	25152 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a.size())
#define BIT(mask, a) ((mask>>(a))&1)
#define MASK(A) (1LL<<(A))
#define ll long long
#define pii pair<int,int>
template <class A,class B> bool maxi(A &a, const B b){if(a < b){a = b; return 1;} return 0;}
template <class A,class B> bool mini(A &a, const B b){if(a > b){a = b; return 1;} return 0;}
const int N = 3e5 + 5, oo = 2e9, MOD = 1e9 + 7;
const ll INF = 1e18;

int n, m;
vector <pii> g[N];
int S, T, U, V;

long long distS[N], distT[N], distX[N], distY[N];

void dijkstra(int st, long long dist[]){
    FOR(i, 1, n) dist[i] = INF;
    #define bg array <long long, 2>
    priority_queue <bg, vector <bg>, greater <bg>> pq;
    pq.push({dist[st] = 0, st});
    while(!pq.empty()){
        int u = pq.top()[1];
        long long cost = pq.top()[0];
        pq.pop();
        if(cost > dist[u]) continue;
        for(pair <int, int> it : g[u]){
            int v = it.first, w = it.second;
            if(dist[v] > cost + w){
                dist[v] = cost + w;
                pq.push({dist[v], v});
            }
        }
    }
    #undef bg
}

long long minX[N], minY[N], ans = INF;

void dfs(int u){
    if(minX[u] != INF) return;
    minX[u] = distX[u];
    minY[u] = distY[u];

    for(pair <int, int> it : g[u]){
        int v = it.first, w = it.second;
        if(distS[u] + w + distT[v] == distS[T]){
            dfs(v);
            minX[u] = min(minX[u], minX[v]);
            minY[u] = min(minY[u], minY[v]);
        }
    }

    mini(ans, distX[u] + minY[u]);
    mini(ans, distY[u] + minX[u]);
}

void process(){
    cin >> n >> m >> S >> T >> U >> V;
    FOR(i, 1, m){
        int u, v, w; cin >> u >> v >> w;
        g[u].emplace_back(make_pair(v, w)); g[v].emplace_back(make_pair(u, w));
    }    

    dijkstra(S, distS);
    dijkstra(T, distT);
    dijkstra(U, distX);
    dijkstra(V, distY); 
    
    ans = distX[V];
    FOR(i, 1, n){
        minX[i] = minY[i] = INF;
    }
    dfs(S);
    cout << ans;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    #define taskname "kieuoanh"
    if(fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    int tc = 1; 
    //cin >> tc;
    while(tc--) process();
    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(taskname".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(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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