Submission #516207

#	Time	Username	Problem	Language	Result	Execution time	Memory
516207		Andy__Andy__	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	904 ms	73608 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;

ifstream f ("test.in");
ofstream g ("test.out");


int S,T,U,V,n,m;
set < array < int , 2> > G[100005];
set < array < int , 2> > Gpass[100005];
set < array < int ,2> > q;
int dpS[100005];
int dpT[100005];
int passNodes[100005];
int ans[100005],opt;

void neig(int dp[],int nod,set < array < int , 2> > GG[])
{
    for(auto x:GG[nod])
    {
        int cost = x[1];
        int vecin = x[0];

        if(dp[nod]+cost<dp[vecin])
        {
            q.erase({dp[vecin],vecin});
            dp[vecin] = dp[nod] + cost;
            q.insert({dp[vecin],vecin});
        }
    }
}

void dij(int dp[] , int start,set < array < int , 2> > GG[])
{
    dp[ start ] = 0;
    q.insert({0,start});

    while(q.size())
    {
        auto x = *(q.begin());

        int nod = x[1];
        int cost = x[0];

        q.erase(q.begin());
        neig(dp,nod,GG);
    }
    return ;
}

void getPassNodes(int start,int target)
{
    passNodes[start] = 1;

    queue < int > coada;

    coada.push(start);

    while(coada.size())
    {
        int nod = coada.front();
        coada.pop();

        passNodes[nod] =1;

        for(auto x:G[nod])
        {
            int cost = x[1];
            int vecin = x[0];

            if(dpS[vecin] + dpT[vecin] <= target and passNodes[vecin] == 0)
            {
                coada.push(vecin);
                //Gpass[nod].push_back({vecin,0});
                //Gpass[vecin].push_back({nod,0});
            }
        }
    }
    return ;
}

int viz[100005];

void solve(int nod ,int target)
{
    viz[nod] =1;
    if(nod == T)
    {
        dij(ans,U,Gpass);
        opt = min(opt,ans[V]);
        return ;
    }

    for(auto x:G[nod])
    {
        int vecin = x[0];
        if(dpS[vecin] + dpT[vecin] <= target and viz[vecin] == 0 )
        {
            viz[vecin] = 1;
            Gpass[vecin].insert({nod,0});
            Gpass[nod].insert({vecin,0});
            solve(vecin,target);
            Gpass[vecin].erase({nod,0});
            Gpass[nod].erase({vecin,0});

        }
    }
    return ;
}


main()
{
    cin>>n>>m;

    cin>>S>>T;
    cin>>U>>V;

    for(int i=1;i<=n;++i) dpS[i] = dpT[i]= ans[i] = opt = 1ll<<62;

    for(int i=1;i<=m;++i)
    {
        int a,b,c;
        cin>>a>>b>>c;
        G[a].insert({b,c});
        Gpass[a].insert({b,c});
        G[b].insert({a,c});
        Gpass[b].insert({a,c});
    }

    dij(dpS,S,G);
    dij(dpT,T,G);
    solve(S,dpS[T]);

    cout<<opt;

    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dij(long long int*, long long int, std::set<std::array<long long int, 2> >*)':
commuter_pass.cpp:45:13: warning: unused variable 'cost' [-Wunused-variable]
   45 |         int cost = x[0];
      |             ^~~~
commuter_pass.cpp: In function 'void getPassNodes(long long int, long long int)':
commuter_pass.cpp:70:17: warning: unused variable 'cost' [-Wunused-variable]
   70 |             int cost = x[1];
      |                 ^~~~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:114:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  114 | main()
      | ^~~~

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