Submission #1118725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118725		Tai_xiu	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	350 ms	37372 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define i128 int128
#define ii pair<int,int>
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pair<int,int>>
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FOR1(i,a,b,c) for (int i=a;i<=b;i+=c)
#define REP(i,a,b) for (int i=a;i>=b;i--)
#define REP1(i,a,b,c) for(int i=b;i>=a;i-=c)
#define endh '\n';
#define len(a) a.length()
#define pb(c) push_back(c)
#define elif else if
#define ppb() pop_back()
#define rong std::npos
#define all(c) (c.begin(),c.end())
#define Z int
#define R double
#define lcm(a,b) ((int) (a/__gcd(a,b))*b)
#define mk(a,b) make_pair(a,b)
Z dx4[]={-1,1,0,0};
Z dy4[]={0,0,1,-1};
string co="YES",khong="NO";
const int mod=1e9+7;
const Z maxn=200005;
Z n,m,s,t,toi,kurumi;
Z ds[maxn],dt[maxn],du[maxn],dv[maxn];
vii g[maxn];
vi g1[maxn];
const Z oo=1e18;
void dijkstra(Z sink,Z d[])
{
    FOR(i,1,n) d[i]=oo;
    d[sink]=0;
    priority_queue<ii,vii,greater<ii>>q;
    q.push(mk(0,sink));
    while(!q.empty()){
        ii top=q.top();q.pop();
        Z u=top.second;
        Z w=top.first;
        if (w>d[u]) continue;
        for (ii i:g[u]){
            Z u1=i.first;
            Z w1=i.second;
            if (d[u]+w1<d[u1]){
                d[u1]=d[u]+w1;
                q.push(mk(d[u1],u1));
            }
        }

    }
}
Z ans=1e18;
Z dp1[maxn],dp2[maxn];
bool check[maxn];
void dfs(Z u)
{
    check[u]=1;
    for (Z v:g1[u]){
        if (check[v]==0){
            dfs(v);
        }
            dp2[u]=min(dp2[v],dp2[u]);
    }
}
void calc(Z d1[],Z d2[])
{
    FOR(i,1,n) dp1[i]=d1[i];
    FOR(i,1,n) check[i]=0;
    FOR(i,1,n) dp2[i]=d2[i];
    FOR(i,1,n) {
        if (check[i]==0) dfs(i);
    }
    FOR(i,1,n){
        ans=min(ans,dp2[i]+d1[i]);
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//    freopen("commuter.inp","r",stdin);
//    freopen("commuter.out","w",stdout);
    cin>>n>>m>>s>>t;
    cin>>toi>>kurumi;
    FOR(i,1,m){
        Z u,v,w;
        cin>>u>>v>>w;;
        g[u].pb(mk(v,w));
        g[v].pb(mk(u,w));
    }
    dijkstra(s,ds);
    dijkstra(t,dt);
    dijkstra(toi,du);
    dijkstra(kurumi,dv);
    FOR(i,1,n){
        for ( ii v:g[i]){
            if (ds[i]+dt[v.first]+v.second==ds[t]) g1[i].pb(v.first);
        }
    }
    calc(du,dv);
    calc(dv,du);
//    FOR(i,1,n) cout<<ds[i]<<" ";
//    cout<<'\n';
//    FOR(i,1,n) cout<<dt[i]<<" ";
//    cout<<'\n';
    cout<<ans;
}

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