Submission #263546

#	Time	Username	Problem	Language	Result	Execution time	Memory
263546		MKopchev	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	758 ms	4048 KiB

ho_t4

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

const int nmax=200+5,mmax=50000+5;

const long long inf=1e16+42;

int n,m;

struct edges
{
    int from,to,cost,to_rev;
};
edges inp[mmax];

vector< pair<int/*dist*/,int/*to*/> > adj[nmax];

long long dist[nmax];

priority_queue< pair<long long/*dist*/,int/*node*/> > pq,idle;

long long dij(int from,int to)
{
    memset(dist,-1,sizeof(dist));

    pq=idle;

    pq.push({0,from});

    while(dist[to]==-1&&pq.size())
    {
        pair<long long/*dist*/,int/*node*/> tp=pq.top();
        pq.pop();

        tp.first=-tp.first;

        if(dist[tp.second]!=-1)continue;

        dist[tp.second]=tp.first;

        for(auto k:adj[tp.second])
            if(dist[k.second]==-1)pq.push({-(tp.first+k.first),k.second});
    }

    //for(int i=1;i<=n;i++)cout<<dist[i]<<" ";cout<<endl;

    if(dist[to]==-1)return inf;
    return dist[to];
}
long long solve(int which)
{
    long long ret=inp[which].to_rev;

    for(int i=1;i<=n;i++)adj[i]={};

    for(int i=1;i<=m;i++)
        if(i!=which)adj[inp[i].from].push_back({inp[i].cost,inp[i].to});
        else adj[inp[i].to].push_back({inp[i].cost,inp[i].from});

    ret=ret+dij(1,n);

    ret=ret+dij(n,1);

    //cout<<"which= "<<which<<" ret= "<<ret<<endl;

    return ret;
}

long long floyd[nmax][nmax];

int main()
{
    scanf("%i%i",&n,&m);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            floyd[i][j]=inf;

    for(int i=1;i<=n;i++)
        floyd[i][i]=0;

    for(int i=1;i<=m;i++)
    {
        scanf("%i%i%i%i",&inp[i].from,&inp[i].to,&inp[i].cost,&inp[i].to_rev);
        floyd[inp[i].from][inp[i].to]=min(floyd[inp[i].from][inp[i].to],1LL*inp[i].cost);
    }

    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                floyd[i][j]=min(floyd[i][j],floyd[i][k]+floyd[k][j]);

    /*
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)cout<<i<<" "<<j<<" -> "<<floyd[i][j]<<endl;
    */

    long long outp=inf;

    outp=min(outp,floyd[1][n]+floyd[n][1]);

    for(int i=1;i<=m;i++)
    {
        long long low_path_1=min(floyd[1][n],floyd[1][inp[i].to]+inp[i].cost+floyd[inp[i].from][n]);

        long long low_path_2=min(floyd[n][1],floyd[n][inp[i].to]+inp[i].cost+floyd[inp[i].from][1]);

        //cout<<i<<" -> "<<low_path_1<<" "<<low_path_2<<" "<<inp[i].to_rev<<" "<<outp<<endl;

        if(low_path_1+low_path_2+inp[i].to_rev<outp)outp=min(outp,solve(i));
    }
    if(outp>=inf)printf("-1\n");
    else printf("%i\n",outp);

    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:113:19: warning: format '%i' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  113 |     else printf("%i\n",outp);
      |                  ~^    ~~~~
      |                   |    |
      |                   int  long long int
      |                  %lli
ho_t4.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |     scanf("%i%i",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
ho_t4.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |         scanf("%i%i%i%i",&inp[i].from,&inp[i].to,&inp[i].cost,&inp[i].to_rev);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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