Submission #788065

#	Time	Username	Problem	Language	Result	Execution time	Memory
788065		prefixorsuuffiixx	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	165 ms	27324 KiB

commuter_pass

//ashoori is my love
//ashoori is my love//ashoori is my love//ashoori is my love//ashoori is my love//ashoori is my love
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef int it;
typedef pair<ll, ll> pii;
typedef pair<ll, pii> piii;
#pragma GCC optimize ("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops,Ofast")
#define sep  "\n"
#define pes  " "
#define int long long
#define print(x,n) for(int i=1; i<=n ; i++)cout<<x[i]<<" "
#define scan(x,n) for(int i=1 ; i<=n ; i++)cin>>x[i]
#define all(x) x.begin(), x.end()
#define pb push_back
#define F first
#define S second
#define sz size
#define cin2(r,j) cin>>r>>j
#define cin1(r) cin>>r
#define cin3(r,j,k) cin>>r>>j>>k
# define InTheNameOfGod                                  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxx=1e5+10;
const ll MOD=1000000007;
const ll inf=1e18;
ll t = 0 , distancess[4][maxx],dpuashoori[maxx],dpvashoori[maxx] , mark1[maxx]  , mark2[maxx] , mark3[maxx] , mark4[maxx] , ans = inf;

pair<ll, ll> p;
int n,m;
vector<pii> g[maxx];
vector<pii> g2[maxx];
void Ashooooor(ll st, ll arr[]) {
	for(int i = 0 ; i < maxx ; i++)arr[i]=inf;

	priority_queue<pair<ll, ll>> pq;
	pq.push({0, st});
	while (!pq.empty()) {
		ll c, node;
		c = pq.top().F;
		node = pq.top().S;
		pq.pop();
		if (!mark1[node]) {
			arr[node] = c;
			mark1[node] = true;
			for (auto i : g[node]) pq.push({ c - i.S, i.F});
		}
	}
}
void ashoori2(ll v , ll u){
    for(int i = 0 ; i < maxx ; i++)dpvashoori[i]=0;
     for(int i = 0 ; i < maxx ; i++)dpuashoori[i]=0;
     priority_queue<piii> pq;
     pq.push({0LL, {v, 0LL}});
	dpvashoori[0]=inf;
	dpuashoori[0]=inf;

	while (!pq.empty()) {
		ll c, node, par;
		c  = pq.top().F;
		p  = pq.top().S;
		node = p.F;
        par = p.S;
		pq.pop();
		//0  - > S  1 - > T  2 -> U 3 -> V
		if (mark1[node]==0) {
			mark1[node] = true;
			distancess[0][node] = -c;
			dpuashoori[node] = min(distancess[2][node], dpuashoori[par]);
			dpvashoori[node] = min(distancess[3][node], dpvashoori[par]);
			for (auto i : g[node]) pq.push({c - i.S, {i.F, node}});
		} else if (-c == distancess[0][node]) {
			if (min(distancess[2][node], dpuashoori[par]) + min(distancess[3][node], dpvashoori[par]) <=
			    dpuashoori[node] + dpvashoori[node]) {
				dpuashoori[node] = min(distancess[2][node], dpuashoori[par]);
				dpvashoori[node] = min(distancess[3][node], dpvashoori[par]);
			}
		}
	}
	ans = min(ans,dpvashoori[u] + dpuashoori[u]);


}
void solve(){
       int n, m,S,T,V,U;
       cin>>n>>m>>S>>T>>V>>U;
       for(int i = 1 ; i <= m ; i++){
            int u ,v,c;
            cin>>u>>v>>c;
            g[u].pb({v,c});
            g[v].pb({u,c});
       }
       for(int j = 0 ; j <= 3 ; j++)
       for(int i = 1 ; i <= n ; i++){
            distancess[j][i]=inf;
       }
       Ashooooor(S, distancess[0]);
       Ashooooor(T, distancess[1]);
       Ashooooor(U, distancess[2]);
       Ashooooor(V, distancess[3]);

    ashoori2(S,T);
    ashoori2(T,S);
    cout<<ans;

}




/*===========================================================================================================================*/
signed main(){
    InTheNameOfGod;
    //int tt = clock();
    //cout << fixed << setprecision(6);

    int tc = 1;
    //cin>>tc;

    //for(int i = 1 ; i <= 3 ; i++)cout<<dp[i]<<" ";
    while(tc--){solve();

        //cerr << "TIME = " << clock() - tt << endl;
        //tt = clock();
        }


}

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