Submission #1216126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216126		kiennguyendinh	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	1578 ms	27776 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
int n,m,S,T,U,V,x,y;
long long res;
long long w;
vector<pair<int,long long>> adj[100001];
long long inf = 1e18;
vector<int> g[100001];
bool c[100001];
long long dist[4][100001];
long long opt[2][100001];
void dik(int t,int sta){
    for(int i = 1;i <= n;i++) dist[t][i] = inf;
    dist[t][sta] = 0;
    queue<int> q;
    q.push(sta);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(pair<int,long long> &v : adj[u]){
            if(dist[t][v.first] > dist[t][u] + v.second){
                dist[t][v.first] = dist[t][u] + v.second;
                q.push(v.first);
            }
        }
    }
}
void build(int u){
    c[u] = true;
    for(pair<int,long long> v : adj[u]){
        if(dist[0][u] + v.second + dist[1][v.first] == dist[0][V]){
            g[u].push_back(v.first);
            if(!c[v.first]) build(v.first);
        }
    }
}
void dfs(int u){
    c[u] = true;
    opt[0][u] = dist[2][u];
    opt[1][u] = dist[3][u];
   for(int v : g[u]){
      if(!c[v]) dfs(v);
      opt[0][u] = min(opt[0][u],opt[0][v]);
      opt[1][u] = min(opt[1][u],opt[1][v]);
   }
   //cout << S << " to " << u << " " <<dist[2][u] << " " << opt[1][u] << "\n";
   //cout << T << " to " << u << " " << dist[3][u] << " " << opt[0][u] << "\n";
   res = min(res,dist[2][u] + opt[1][u]);
   res = min(res,dist[3][u] + opt[0][u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> U >> V >> S >> T;
    for(int i = 1;i <= m;i++){
        cin >> x >> y >> w;
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
    }
    dik(0,U);
    dik(1,V);
    dik(2,S);
    dik(3,T);
    build(U);
    res = dist[2][T];
    for(int i = 1;i <= n;i++) c[i] = false;
    dfs(U);
    cout << res;
    return 0;
}

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