Submission #245475

#	Time	Username	Problem	Language	Result	Execution time	Memory
245475		uacoder123	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	1096 ms	3960 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];
lli n,m;
vi ap[2];
void floyd(lli t,lli e)
{
  if(e>1)
    floyd(t,e-1);
  for(lli i=1;i<=n;++i)
  {
    for(lli j=1;j<=n;++j)
    {
      arr1[i][j]=arr[i][j];
      for(lli k=0;k<al[i].size();++k)
      {
        if(t==1&&p[0][i][k]==1)
          arr1[i][j]=10000000000000000;
        else if(t==2&&p[1][i][k]==1)
          arr1[i][j]=10000000000000000;
        else
        arr1[i][j]=min(arr1[i][j],al[i][k].S+arr[al[i][k].F][j]);
      }
    }
  }
  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];
  ii lu[201];
  for(lli i=0;i<201;++i)
  {
    lu[i]=mp(0,0);
    d[i]=10000000000000000;
  }
  set<ii> s;
  s.insert(mp(0,so));
  lu[so]=mp(so,0);
  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]=mp(v.S,i);
       s.insert(mp(d[al[v.S][i].F],al[v.S][i].F)); 
      }
    }
  }
  if(lu[te].F!=0)
  {
    int it=n+1;
    while(te!=so)
    {
      if(te==it)
        exit(1);
      ap[t].pb(te);
      p[t][lu[te].F][lu[te].S]=1;
      it=te;
      te=lu[te].F;
    }
    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)
        {
          if(i==j)
            arr[i][j]=0;
          else
            arr[i][j]=10000000000000000;
          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;
    lli d[201][m];
    for(lli i=0;i<m;++i)
    {
      lli f,s,w,k;
      cin>>f>>s>>w>>k;
      al[f].pb(mp(s,w));
      d[f][int(al[f].size())-1]=k;
    }
    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[1].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+d[i][j]);
      }
    }
    if(ans>=10000000000000000)
      cout<<"-1"<<endl;
    else
      cout<<ans<<endl;
    exit(0);
  }
  return(0);
}

Compilation message (stderr)

ho_t4.cpp: In function 'void floyd(lli, lli)':
ho_t4.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(lli k=0;k<al[i].size();++k)
                   ~^~~~~~~~~~~~~
ho_t4.cpp: In function 'void dij(lli, lli, lli)':
ho_t4.cpp:68: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 'int main()':
ho_t4.cpp:136:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(lli j=0;j<al[i].size();++j)
                   ~^~~~~~~~~~~~~
ho_t4.cpp:144:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for(lli k=0;k<ap[1].size();++k)
                       ~^~~~~~~~~~~~~
ho_t4.cpp:161: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