Submission #245513

#	Time	Username	Problem	Language	Result	Execution time	Memory
245513		uacoder123	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	54 ms	6264 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
 
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
lli dis[3][201][201];
vector<ii> al[201];
int p[2][201][201]={};
lli arr[201][201],arr1[201][201],co=0;
lli n,m;
vi ap[2];
lli d1[201][500000];
void floyd(lli t,lli e)
{
  for(lli i=1;i<=n;++i)
  {
    co++;
    for(lli j=1;j<=n;++j)
    {
      arr1[i][j]=arr[i][j];
      for(lli k=1;k<=n;++k)
      {
        arr1[j][k]=min(arr1[j][k],arr[j][i]+arr[i][k]);
      }
    }
  }
  swap(arr,arr1);
  if(e==n-1)
  {
    for(lli i=1;i<=n;++i)
      for(lli j=1;j<=n;++j)
      {
        dis[t][i][j]=arr[i][j];
      }
  }
}
void dij(lli t,lli so,lli te)
{
  lli d[201];
  int lu[201];
  for(lli i=0;i<201;++i)
  {
    lu[i]=0;
    d[i]=10000000000000000;
  }
  set<ii> s;
  s.insert(mp(0,so));
  lu[so]=so;
  while(s.size()!=0)
  {
    ii v=(*s.begin());
    d[v.S]=v.F;
    s.erase(s.begin());
    for(lli i=0;i<al[v.S].size();++i)
    {
      if(d[al[v.S][i].F]>al[v.S][i].S+v.F)
      {
       s.erase(mp(d[al[v.S][i].F],al[v.S][i].F));
       d[al[v.S][i].F]=al[v.S][i].S+v.F;
       lu[al[v.S][i].F]=v.S;
       s.insert(mp(d[al[v.S][i].F],al[v.S][i].F)); 
      }
    }
  }
  if(lu[te]!=0)
  {
    int it=n+1;
    while(te!=so)
    {
      if(te==it)
        exit(1);
      ap[t].pb(te);
      p[t][lu[te]][te]=1;
      it=te;
      te=lu[te];
    }
    ap[t].pb(so);
    }
  reverse(all(ap[t]));
}
void set1(int t)
{
  for(lli i=1;i<=n;++i)
      {
        for(lli j=1;j<=n;++j)
        {
          auto it=(lower_bound(all(al[i]),mp(j,0*1LL)))-al[i].begin();
          if(i==j)
            arr[i][j]=0;
          else
            arr[i][j]=10000000000000000;
          if(it<al[i].size()&&al[i][it].F==j)
          {
            arr[i][j]=al[i][it].S;
            if(t==1&&p[0][i][j]==1)
            {
              arr[i][j]=10000000000000000;
              it++;
            }
          if(it<al[i].size()&&al[i][it].F==j)
            arr[i][j]=al[i][it].S;
          if(t==2&&p[1][i][j]==1)
            {
              arr[i][j]=10000000000000000;
              it++;
            }
          if(it<al[i].size()&&al[i][it].F==j)
            arr[i][j]=al[i][it].S;
          }
          dis[t][i][j]=10000000000000000;
        }
      }
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  lli test=1;
  for(;test>0;--test)
  {
    cin>>n>>m;
    for(lli i=0;i<m;++i)
    {
      lli f1,s1,w1,k1;
      cin>>f1>>s1>>w1>>k1;
      al[f1].pb(mp(s1,w1));
      d1[f1][int(al[f1].size())-1]=k1;
    }
    dij(0,1,n);
    dij(1,n,1);
    set1(0);
    floyd(0,n);
    set1(1);
    floyd(1,n);
    set1(2);
    floyd(2,1);
    lli ans=dis[0][1][n]+dis[0][n][1];
    for(lli i=1;i<=n;++i)
    {
      for(lli j=0;j<al[i].size();++j)
      {
        lli ans1=dis[0][1][n],ans2=dis[0][n][1];
        if(p[0][i][j]!=1)
          ans1=min(ans1,al[i][j].S+dis[0][1][al[i][j].F]+dis[0][i][n]);
        else
        {
          ans1=10000000000000000;
          for(lli k=0;k<ap[0].size();++k)
          {
            for(lli l=int(ap[0].size())-1;l>=0;--l)
            {
              ans1=min(ans1,dis[0][1][ap[0][k]]+dis[1][ap[0][k]][ap[0][l]]+dis[0][ap[0][l]][n]);
              if(al[i][j].F==ap[0][l])
                break;
            }
            if(ap[0][k]==i)
              break;
          }
        }
        if(p[1][i][j]!=1)
          ans2=min(ans2,al[i][j].S+dis[0][n][al[i][j].F]+dis[0][i][1]);
        else
        {
          ans2=10000000000000000;
          for(lli k=0;k<ap[1].size()-1;++k)
          {
            for(lli l=int(ap[1].size())-1;l>=0;--l)
            {
              ans2=min(ans2,dis[0][n][ap[1][k]]+dis[2][ap[1][k]][ap[1][l]]+dis[0][ap[1][l]][1]);
              if(al[i][j].F==ap[1][l])
                break;
            }
            if(ap[1][k]==i)
              break;
          }
        }
        ans=min(ans,ans1+ans2+d1[i][j]);
      }
    }
    if(ans>=10000000000000000)
      cout<<"-1"<<endl;
    else
      cout<<ans<<endl;
  }
  return(0);
}

Compilation message (stderr)

ho_t4.cpp: In function 'void dij(lli, lli, lli)':
ho_t4.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(lli i=0;i<al[v.S].size();++i)
                 ~^~~~~~~~~~~~~~~
ho_t4.cpp: In function 'void set1(int)':
ho_t4.cpp:103:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           if(it<al[i].size()&&al[i][it].F==j)
              ~~^~~~~~~~~~~~~
ho_t4.cpp:111:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           if(it<al[i].size()&&al[i][it].F==j)
              ~~^~~~~~~~~~~~~
ho_t4.cpp:118:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           if(it<al[i].size()&&al[i][it].F==j)
              ~~^~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:151:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(lli j=0;j<al[i].size();++j)
                   ~^~~~~~~~~~~~~
ho_t4.cpp:159:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for(lli k=0;k<ap[0].size();++k)
                       ~^~~~~~~~~~~~~
ho_t4.cpp:176:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for(lli k=0;k<ap[1].size()-1;++k)
                       ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63