Submission #1065616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065616		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	214 ms	30636 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=(j);i<=(k);i++)
#define for2(i,j,k) for(int i=(j);i>=(k);i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2e5+6;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=123456789;

int n,m,q;
int A,B,C,D,bac[maxn],preC[maxn],preD[maxn];
vector<int> disC,disD,disA,disB;
vector<pii>adj[maxn];
vector<int> ke[maxn];

priority_queue<pii,vector<pii>,greater<pii>> pq;
void dijkstra(int u,vector<int>& dis)
{
    dis.resize(n+1,inf);
    dis[u]=0;
    pq.push({0,u});
    while (!pq.empty())
    {
        int u=pq.top().se,_=pq.top().fi;
        pq.pop();
        if (_!=dis[u]) continue;
        for(auto [v,w]: adj[u])
        {
            if (dis[u]+w<dis[v])
            {
                dis[v]=dis[u]+w;
                pq.push({dis[v],v});
            }
        }
    }
}
inline bool chk(int u) {return ((disA[u]+disB[u])==disA[B]);}
void sol()
{
    cin >> n>> m>> A>>B>>C>>D;
    for1(i,1,m)
    {
        int u,v,w; cin >> u>> v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    dijkstra(A,disA);
    dijkstra(B,disB);
    dijkstra(C,disC);
    dijkstra(D,disD);
    for1(u,1,n)
    {
        if (chk(u))
        {
            for (auto [v,w]: adj[u])
            {
                if (chk(v) && disA[v]==disA[u]+w)
                {
                    ke[u].pb(v);
                    bac[v]++;
                }
            }
        }
    }
    for1(i,1,n)
    {
        preC[i]=disC[i];
        preD[i]=disD[i];
    }
    int res=disC[D];
    vector<int> L;
    L.pb(1);
    while (!L.empty())
    {
        int u=L.back();
        L.pop_back();
        res=min(res,min(preC[u]+disD[u],preD[u]+disC[u]));
        for(int v: ke[u])
        {
            preC[v]=min(preC[v],preC[u]);
            preD[v]=min(preD[v],preD[u]);
            bac[v]--;
            if (bac[v]==0)
            {
                L.pb(v);
            }
        }
    }
    cout << res;

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("PAINT.inp","r",stdin);
//    freopen("PAINT.out","w",stdout);
    int t=1;//cin>>t;
    while (t--)
    {
        sol();
    }
}
/*
*/

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