oj.uz

Submission #263534

# Submission time Handle Problem Language Result Execution time Memory
263534 2020-08-13T18:57:49 Z MKopchev Olympic Bus (JOI20_ho_t4) C++14
5 / 100
 1000 ms 3452 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 42 ms 384 KB Output is correct
4 Correct 55 ms 360 KB Output is correct
5 Correct 36 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 30 ms 384 KB Output is correct
10 Correct 103 ms 504 KB Output is correct
11 Correct 94 ms 384 KB Output is correct
12 Correct 102 ms 384 KB Output is correct
13 Correct 60 ms 384 KB Output is correct
14 Correct 69 ms 444 KB Output is correct
15 Correct 47 ms 384 KB Output is correct
16 Correct 70 ms 384 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 3452 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 384 KB Output is correct
2 Correct 2 ms 396 KB Output is correct
3 Execution timed out 1070 ms 2448 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 42 ms 384 KB Output is correct
4 Correct 55 ms 360 KB Output is correct
5 Correct 36 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 30 ms 384 KB Output is correct
10 Correct 103 ms 504 KB Output is correct
11 Correct 94 ms 384 KB Output is correct
12 Correct 102 ms 384 KB Output is correct
13 Correct 60 ms 384 KB Output is correct
14 Correct 69 ms 444 KB Output is correct
15 Correct 47 ms 384 KB Output is correct
16 Correct 70 ms 384 KB Output is correct
17 Execution timed out 1098 ms 3452 KB Time limit exceeded
18 Halted 0 ms 0 KB -