Submission #263534

#	Time	Username	Problem	Language	Result	Execution time	Memory
263534		MKopchev	Olympic Bus (JOI20_ho_t4)	C++14	5 / 100	1098 ms	3452 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;
}
int main()
{
    scanf("%i%i",&n,&m);

    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);

    long long outp=inf;

    for(int i=0;i<=m;i++)
        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:81:19: warning: format '%i' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   81 |     else printf("%i\n",outp);
      |                  ~^    ~~~~
      |                   |    |
      |                   int  long long int
      |                  %lli
ho_t4.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |     scanf("%i%i",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
ho_t4.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |         scanf("%i%i%i%i",&inp[i].from,&inp[i].to,&inp[i].cost,&inp[i].to_rev);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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