Submission #1070860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070860		dosts	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	368 ms	48772 KiB

commuter_pass

//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e18;
const int N = 1e5+50;
int n;
vector<pii> edges[N];


vi dijkstra(int root) {
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    vi dists(n+1,inf);
    pq.push({0,root});
    dists[root] = 0;
    while (!pq.empty()) {
        pii f = pq.top();
        pq.pop();
        if (dists[f.ss] < f.ff) continue;
        for (auto it : edges[f.ss]) {
            if (dists[it.ff] > f.ff+it.ss) {
                dists[it.ff] = f.ff+it.ss;
                pq.push({f.ff+it.ss,it.ff});
            }
        }
    } 
    return dists;
}

void solve() { 
    int m;
    cin >> n >> m;
    int a,b,s,t;
    cin >> a >> b >> s >> t;
    for (int i=1;i<=m;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    vi da = dijkstra(a);
    vi db = dijkstra(b);
    using state = pair<int,pair<int,pair<pii,int>>>;
    int dp[n+1][2][2][2];
    for (int i=0;i<=n;i++) {
        for (int j=0;j<2;j++) {
            for (int jj=0;jj<2;jj++) {
                for (int jjj=0;jjj<2;jjj++) {
                    dp[i][j][jj][jjj] = inf;
                }
            }
        }
    }
    dp[s][0][0][0] = 0;
    priority_queue<state,vector<state>,greater<state>> pq;
    pq.push({0,{s,{{0,0},0}}});
    while (!pq.empty()) {
        state f = pq.top();
        int city = f.ss.ff;
        int cost = f.ff;
        int ever = f.ss.ss.ff.ff;
        int cur =  f.ss.ss.ff.ss;
        int dir = f.ss.ss.ss;
        pq.pop();
        if (dp[city][ever][cur][dir] < cost) continue;
        if (!(ever && !cur)) {
            for (auto& [go,w] : edges[city]) {
                if ((da[city]+w+db[go]!=da[b] && db[city]+w+da[go] != da[b])) continue;
                if (ever && (dir != db[go]>db[city])) continue;
                if (dp[go][1][cur|1][db[go]>db[city]] > cost){
                    dp[go][1][cur|1][db[go]>db[city]] = cost;
                    pq.push({cost,{go,{{1,cur|1},db[go]>db[city]}}});
                }
            }
        }
        for (auto& [go,w] : edges[city]) {
            if (dp[go][ever][0][dir] > cost+w){
                dp[go][ever][0][dir] = cost+w;
                pq.push({cost+w,{go,{{ever,0},dir}}});
            }
        }     
    }
    int ans = inf;
    for (int i=0;i<2;i++) for (int j=0;j<2;j++) for (int jj=0;jj<2;jj++) ans = min(ans,dp[t][i][j][jj]);
    cout << ans << '\n';
}
 
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:75:43: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
   75 |                 if (ever && (dir != db[go]>db[city])) continue;

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