Submission #1224126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224126		Bui_Quoc_Cuong	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2101 ms	327680 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], dist[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 dijkstradag(int st, int ed, long long distST[], long long distED[], int X, int Y){
    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(distST[u] + w + distED[v] == distED[X]) w = 0;
            if(dist[v] >= cost + w){
                dist[v] = cost + w;
                pq.push({dist[v], v});
            }
        }
    }       
    #undef bg
    return dist[ed];
}

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);

    long long ans = dijkstradag(U, V, distS, distT, S, T);
    ans = min(ans, dijkstradag(U, V, distT, distS, T, S));
    ans = min(ans, dijkstradag(V, U, distS, distT, S, T));
    ans = min(ans, dijkstradag(V, U, distT, distS, T, 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: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45