Submission #74037

#	Time	Username	Problem	Language	Result	Execution time	Memory
74037		Bodo171	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	977 ms	87412 KiB

commuter_pass

#include <iostream>
#include <fstream>
#include <queue>
#include <climits>
#include <vector>
using namespace std;
const int nmax=100005;
priority_queue< pair<long long,int> > pq;
vector< pair<int,long long> > v[nmax];
long long dS[nmax],dT[nmax],dd[4*nmax];
int i,n,x,nod,newhow,how,s,t,u,vv,m,a,b,c;
long long di,D,dist;
void dij(int source,long long d[])
{
    for(i=1;i<=n;i++)
        d[i]=LLONG_MAX;
    d[source]=0;
    pq.push({0,source});
    while(!pq.empty())
    {
        x=pq.top().second;di=-pq.top().first;
        pq.pop();
        for(i=0;i<v[x].size();i++)
        {
            nod=v[x][i].first;D=di+v[x][i].second;
            if(D<d[nod])
            {
                d[nod]=D;
                pq.push({-D,nod});
            }
        }
    }
}
void exs()
{
    for(int i=0;i<v[x].size();i++)
    {
         nod=v[x][i].first;D=di+v[x][i].second;
         newhow=3*(how!=0);
         if(D<dd[nod*4+newhow])
         {
             dd[nod*4+newhow]=D;
             pq.push({-D,nod*4+newhow});
         }
    }
}
bool ok(int par,int A,int B,long long len)
{
    if(par==1)
    {
        return (dS[A]+dT[B]+len==dist&&dS[A]<dS[B]);
    }
    else
    {
        return (dT[A]+dS[B]+len==dist&&dT[A]<dT[B]);
    }
}
void ex(int par)
{
      for(int i=0;i<v[x].size();i++)
    {
         nod=v[x][i].first;D=di;
         if(D<dd[nod*4+par]&&ok(par,x,nod,v[x][i].second))
         {
             dd[nod*4+par]=D;
             pq.push({-D,nod*4+par});
         }
    }
}
long long calc()
{
    //0-drum normal
    //1- de la s la t
    //2-de la t la s
    //3-drum normal din nou
    for(i=1;i<=4*n+5;i++)
        dd[i]=LLONG_MAX;
    dd[4*u]=0;
    pq.push({0,4*u});
    while(!pq.empty())
    {
        x=((pq.top().second)>>2);how=((pq.top().second)&3);
        di=-pq.top().first;
        pq.pop();
        if(x==vv)
            return di;
        if(how==0)
        {
            exs();
            ex(1);
            ex(2);
        }
        if(how==1)
        {
            ex(1);
            exs();
        }
        if(how==2)
        {
            ex(2);
            exs();
        }
        if(how==3)
        {
            exs();
        }
    }
    return 0;
}
int main()
{
   // freopen("data.in","r",stdin);
    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>vv;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    dij(s,dS);
    dij(t,dT);
    dist=dS[t];
    cout<<calc();
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dij(int, long long int*)':
commuter_pass.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void exs()':
commuter_pass.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'void ex(int)':
commuter_pass.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<v[x].size();i++)
                   ~^~~~~~~~~~~~

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