Submission #254692

#	Time	Username	Problem	Language	Result	Execution time	Memory
254692		Atill83	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	493 ms	29764 KiB

commuter_pass

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 1e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, m;
ll d[4][MAXN];
ll k[2][MAXN][2];
priority_queue<pll, vector<pll>, greater<pll>> pq;
vector<pll> adj[MAXN];
void dks(int st, int src){
    for(int i = 1; i <= n; i++){
        d[st][i] = INF;
    }
    pq.push({0, src});
    d[st][src] = 0;
    while(!pq.empty()){
        pll cur = pq.top();
        pq.pop();
        for(pll u: adj[cur.ss]){
            if(cur.ff + u.ss < d[st][u.ff]){
                d[st][u.ff] = cur.ff + u.ss;
                pq.push({cur.ff + u.ss, u.ff});
            }
        }
    }
}

ll mn[MAXN][2][2]; // 0 u 1 v
bool visited[MAXN][2];
void dfs(int x, int st){
    visited[x][st] = 1;
    mn[x][st][0] = min(mn[x][st][0], d[2][x]);
    mn[x][st][1] = min(mn[x][st][1], d[3][x]);
    for(pll j: adj[x]){
        if(d[st][j.ff] == d[st][x] + j.ss){
            mn[j.ff][st][0] = min(mn[j.ff][st][0], mn[x][st][0]);
            mn[j.ff][st][1] = min(mn[j.ff][st][1], mn[x][st][1]);
            if(visited[j.ff][st] == 0){
                dfs(j.ff, st);
            }
        }
    }
}




int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>m;
    int s, t, u, v;
    cin>>s>>t>>u>>v;
    memset(mn, 0x7f, sizeof(mn));
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin>>a>>b>>c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    dks(0, s);
    dks(1, t);
    dks(2, u);
    dks(3, v);

    //return 0;
    dfs(s, 0);
    dfs(t, 1);
    ll ans = d[2][v];
    for(int j = 1; j <= n; j++){
        for(pll &i: adj[j]){
            if(d[0][i.ff] + i.ss + d[1][j] == d[0][t]){
                ans = min({ans, mn[i.ff][0][1] + mn[j][1][0], mn[i.ff][0][0] + mn[j][1][1]});
            }else if(d[0][j] + i.ss + d[1][i.ff] == d[0][t]){
                ans = min({ans, mn[i.ff][1][1] + mn[j][0][0], mn[i.ff][1][0] + mn[j][0][1]});
            }
        }
    }

    cout<<ans<<endl;



    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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