Submission #1253907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253907		phatdu12345	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	9 ms	17732 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>

const int MAXN = 2e5 + 7;
const int inf = 1e18;

int n, m, s, t, x, y;
vector<pii> a[MAXN];
int dist1[MAXN], dist2[MAXN]; 
int dist[MAXN][2][4]; 

template <typename T>
    bool maximize(T &a, const T &b){
        if(a < b){
            a = b;
            return 1;
        }
        return 0;
    }
    
template <typename T>
    bool minimize(T &a, const T &b){
        if(a > b){
            a = b;
            return 1;
        }
        return 0;
    }

void dijkstra(int start, int dist[]){
    fill(dist + 1, dist + 1 + n, inf);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[start] = 0;
    pq.push({0, start});
    while (!pq.empty()){
        auto [du, u] = pq.top(); pq.pop();
        if (du != dist[u]) continue;
        for (auto [v, w] : a[u]){
            if (dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

struct State{
    int u, cost, check, status; 
    bool operator < (const State &o) const{
        return cost > o.cost; 
    }
};

void dijkstra2(){
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<State> pq;
    dist[x][0][0] = 0;
    pq.push({x, 0, 0, 0});
    // u - d_u - check - status
    // status = 0 --> chưa đi qua cạnh shortest path nào
    // status = 1 --> đi qua cạnh shortest path CÙNG CHIỀU
    // status = 2 --> đi qua cạnh shortest path NGƯỢC CHIỀU
    // check = 1, trước đó đang ở cạnh shortest path và rẽ qua cạnh ko phải shortest path ==> lượt sau ko được rẽ vào nx
    while (!pq.empty()){
        State cur = pq.top(); pq.pop();
        int u = cur.u, d_u = cur.cost, check = cur.check, status = cur.status;
        if (d_u != dist[u][check][status]) continue;

        for (auto [v, w] : a[u]){
            bool case1 = 0, case2 = 0;
            if (dist1[u] + w + dist2[v] == dist1[t]) case1 = 1;
            if (dist1[v] + w + dist2[u] == dist1[t]) case2 = 1;
            // u - d_u - check - status
            if(!check){
                if((status == 0 or status == 2) and case2){
                    if(dist[v][check][2] > dist[u][check][status]){
                        dist[v][check][2] = dist[u][check][status];
                        pq.push({v, dist[v][check][2], check, 2});
                    }
                }  
                if((status == 0 or status == 1) and case1){
                    if(dist[v][check][1] > dist[u][check][status]){
                        dist[v][check][1] = dist[u][check][status];
                        pq.push({v, dist[v][check][1], check, 1});
                    }
                }
                if(status){
                    if(dist[v][check ^ 1][status] > dist[u][check][status] + w){
                        dist[v][check ^ 1][status] = dist[u][check][status] + w;
                        pq.push({v, dist[v][check ^ 1][status], check ^ 1, status});
                    }
                }
                if(!status){
                    if(dist[v][check][status] > dist[u][check][status] + w){
                        dist[v][check][status] = dist[u][check][status] + w;
                        pq.push({v, dist[v][check][status], check, status});
                    }
                }
            }
            
            else if(dist[v][check][status] > dist[u][check][status] + w){
                    dist[v][check][status] = dist[u][check][status] + w;
                    pq.push({v, dist[v][check][status], check, status});
                    
            }
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("path.inp", "r", stdin);
    freopen("path.out", "w", stdout);
    cin >> n >> m >> s >> t >> x >> y;
    for (int i = 1; i <= m; i++){
        int u, v, w; cin >> u >> v >> w;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
    }

    dijkstra(s, dist1);
    dijkstra(t, dist2);
    dijkstra2();

    int ans = LLONG_MAX;
    for(int check = 0; check <= 1; check++)
        for(int status = 0; status <= 2; status++)
            minimize(ans, dist[y][check][status]);
    cout << ans;
}

Compilation message (stderr)

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

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