Submission #1149818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149818		murpyl	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	188 ms	30092 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long 
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define endl "\n"
#define mp make_pair
void setIO(string name = "") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(sz(name)){
		freopen((name+".in").c_str(), "r", stdin); 
		freopen((name+".out").c_str(), "w", stdout);
	}
}


const int maxn = 1e5+10;
const int inf = 1e18;
vector<pi> adj[100010];
int n,m,s,t,u,v;
vi du(maxn), dv(maxn), dend(maxn);
int ans;
vector<bool> visited(maxn);
vector<vi> dp(maxn, vi(2, 0));

void dj1(int start, vi&arr){
    fill(arr.begin(), arr.end(), inf);

    priority_queue<pi, vector<pi>, greater<pi>> pq;
    pq.push({0, start});
    arr[start] = 0;
    while (!pq.empty()){
       // cout<<1<<endl;
        auto [c, node] = pq.top();
        pq.pop();
        if (c > arr[node]) continue;
        for (auto i : adj[node]){
            if (arr[i.first] > c + i.second){
                arr[i.first] = c + i.second;
                pq.push({arr[i.first], i.first});
            }
        }
    }
}


void dj2(int start, int end){
    dp.rsz(n+1, vi(2, inf));
    visited.rsz(n+1, false);
    priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq;
    pq.push({0, {start, 0}});
    dp[0][0] = dp[0][1] = inf;
    while (!pq.empty()){
        //cout<<2<<endl;
        auto [cost, node ] = pq.top();
        auto [cur, parent] = node;
        pq.pop();
        if (!visited[cur]){
            visited[cur] = true;
            dp[cur][0] = min(du[cur], dp[parent][0]);
            dp[cur][1] = min(dv[cur], dp[parent][1]);
            dend[cur] = cost;
            for (auto i : adj[cur]){
                pq.push({cost + i.second, {i.first, cur}});
            }
        }
        else if (cost == dend[cur]){
            if (min(du[cur], dp[parent][0]) + min(dv[cur], dp[parent][1]) <= dp[cur][0] + dp[cur][1]){
                dp[cur][0] = min(du[cur], dp[parent][0]);
                dp[cur][1] = min(dv[cur], dp[parent][1]);
            }
        }

    }
    ans = min(ans, dp[end][0] + dp[end][1]);
}


signed main(){
    setIO();
    cin>>n>>m>>s>>t>>u>>v;
    for (int i = 0; i < m; i++){
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
    du.rsz(n+1);
    dv.rsz(n+1);

    dj1(u, du);
    dj1(v, dv);
    ans = du[v]; 
    dj2(s,t);
    dj2(t,s);
    cout<<ans<<endl;

}

Compilation message (stderr)

commuter_pass.cpp: In function 'void setIO(std::string)':
commuter_pass.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen((name+".in").c_str(), "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen((name+".out").c_str(), "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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