Submission #765133

#	Time	Username	Problem	Language	Result	Execution time	Memory
765133		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++11	0 / 100	2085 ms	48464 KiB

commuter_pass

    /*
Muqalzhar taui
*/
#include <bits/stdc++.h>
#include <iomanip>
 
#define ll long long
#define pb push_back
#define F first
#define S second
#define nl '\n'
#define all(x) x.begin(), x.end()
 
const int N = 2e5 + 7;
const int modd = 1e9 + 7;
const int INF = 1e9 + 7;
const double pi = 3.141592653589793238462643383279502884197;
const double EPS = 0.0000000000001;
using namespace std;
  
int gcd(int a, int b){
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
 
ll binpow(ll a, ll x){
    if(x == 0) return 1;
    if(x % 2 == 0){
        ll y = binpow(a, x / 2);
        return (y * y);
    }
    else{
        return (binpow(a, x - 1) * a);
    }
}

ll n, m, s, t, u, v;
ll a[N], b[N], c[N];
vector <pair <ll, ll>> e[N];
ll pr[N];
ll dst[N];
map <pair <ll, ll>, bool> mp;
bool used[N];

void dfs(ll x){
    used[x] = 1;

    for(auto to : e[x]){
        if(used[to.F] == 0){
            pr[to.F] = x;
            dfs(to.F);
        }
    }
}

void Muqaltin(){  
    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 1; i <= m; i++){
        cin >> a[i] >> b[i] >> c[i];
        e[a[i]].pb({b[i], c[i]});
        e[b[i]].pb({a[i], c[i]});
    }
    dfs(1);
    ll x = t;
    while(x != s){
        mp[{x, pr[x]}] = 1;
        x = pr[x];
    }
    for(int i = 1; i <= n; i++){
        dst[i] = INF;
    }
    queue <ll> q;
    q.push(u);
    dst[u] = 0;
    while(!q.empty()){
        ll res = q.front();
        q.pop();

        for(auto to : e[res]){
            if(mp[{res, to.F}] == 1 || mp[{to.F, res}] == 1){
                // cout << res << " " << to.F << nl;
                if(dst[to.F] > dst[res]){
                    q.push(to.F);
                    dst[to.F] = dst[res];
                }
            }
            else{
                // cout << res << " " << to.F << nl;
                if(dst[to.F] > dst[res] + to.S){
                    q.push(to.F);
                    dst[to.F] = dst[res] + to.S;
                    // cout << res << " " << to.F << " " << dst[to.F] << nl;
                } 
            }
        }
    }
    cout << dst[v];
    return;
}
 
int main(){
    // freopen("pails.in", "r", stdin);
    //  freopen("pails.out", "w", stdout);
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t = 1;
    // cin >> t;
    while(t--){
        Muqaltin();
    }
    return 0;
}

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