Submission #502383

#	Time	Username	Problem	Language	Result	Execution time	Memory
502383		kevin	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	719 ms	20740 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define nl cout<<"\n"
#define f first
#define s second
#define ca(v) for(auto i:v) cout<<i<<" ";

const int MAXN = 1e5 + 5;

int n, m, S, T, U, V;

vector<pair<int, int>> adj[MAXN];
ll dst[MAXN][4];
ll vis[MAXN][3];
ll ans;
ll bst;
void dijkstra(int x, int p){
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    for(int i=0; i<n; i++) dst[i][p] = 2e18;
    dst[x][p] = 0;
    q.push({0, x});
    while(q.size()){
        auto c = q.top(); q.pop();
        int x = c.s; ll w = c.f;
        if(dst[x][p] < w) continue;
        for(auto a : adj[x]){
            if(w + a.s < dst[a.f][p]){
                dst[a.f][p] = w + a.s;
                q.push({dst[a.f][p], a.f});
            }
        }
    }
}
struct nd{
    int x; ll w; int id;
    friend bool operator<(nd a, nd b){ return a.x > b.x; }
};
void solve(){
    for(int i=0; i<n; i++) vis[i][0] = vis[i][1] = vis[i][2] = 2e18;
    vis[S][0] = 0;
    priority_queue<nd> q;
    q.push({S, 0, 0});
    while(q.size()){
        auto c = q.top(); q.pop();
        if(vis[c.x][c.id] < c.w) continue;
        for(auto a:adj[c.x]){
            if(dst[c.x][0] + a.s + dst[a.f][1] == bst){
                if(c.w < vis[a.f][c.id]){
                    vis[a.f][c.id] = c.w;
                    q.push({a.f, c.w, c.id});
                }
            }
        }
        if(c.id == 1){
            // cout<<c.x<<" "<<c.w<<" "<<c.id<<"\n";
            ans = min(ans, c.w + dst[c.x][3]);
        }
        else if(c.id == 2){
            ans = min(ans, c.w + dst[c.x][2]);
        }
        else{
            if(dst[c.x][2]<vis[c.x][1]) q.push({c.x, dst[c.x][2], 1});
            if(dst[c.x][3]<vis[c.x][2]) q.push({c.x, dst[c.x][3], 2});
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
    cin>>n>>m;
    cin>>S>>T>>U>>V; 
    S--; T--; U--; V--;
    for(int i=0; i<m; i++){
        int u, v, x; cin>>u>>v>>x;
        u--; v--;
        adj[u].push_back({v, x});
        adj[v].push_back({u, x});
    }
    dijkstra(S, 0);
    dijkstra(T, 1);
    dijkstra(U, 2);
    dijkstra(V, 3);
    // for(int i=0; i<n; i++) cout<<dst[i][1]<<" ";
    bst = dst[T][0];
    ans = dst[V][2];
    solve();
    cout<<ans;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:73:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
      |                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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