oj.uz

Submission #224102

# Submission time Handle Problem Language Result Execution time Memory
224102 2020-04-17T08:04:22 Z tqbfjotld Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 104 ms 1784 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 500000000000LL

int n,m;
int dist[205];
vector<pair<int,int> > adjl[205];
vector<pair<int,int> > rev[205];
int c[50005];
int d[50005];
int adjm[405][405];

main(){
    scanf("%lld%lld",&n,&m);
    for (int x = 0; x<=2*n; x++){
        for (int y = 0; y<=2*n; y++){
            adjm[x][y] = INF;
            if (x==y) adjm[x][y] = 0;
        }
    }
    for (int x = 0; x<m; x++){
        int a,b,c,d;
        scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
        adjm[a][b] = min(adjm[a][b],c);
        adjm[a+n][b+n] = min(adjm[a+n][b+n],c);
        adjm[b][a+n] = min(adjm[b][a+n],c+d);
    }
    for (int k = 1; k<=2*n; k++){
        for (int i = 1; i<=2*n; i++){
            for (int j = 1; j<=2*n; j++){
                adjm[i][j] = min(adjm[i][j],adjm[i][k]+adjm[k][j]);
            }
        }
    }

    int ans1 = min(adjm[1][n]+adjm[n][1],adjm[1][2*n]+adjm[2*n][n+1]);
    ans1 = min(ans1,adjm[1][n]+adjm[n][n+1]);
    assert(adjm[n+1][n+n] == adjm[1][n]);
    assert(ans1>=0);
    printf("%lld",ans1>=INF?-1:ans1);
    return 0;
    if (m<1000){
        for (int x = 0; x<m; x++){
            int a,b;
            scanf("%lld%lld%lld%lld",&a,&b,&c[x],&d[x]);
            adjl[a].push_back({b,x});
            rev[b].push_back({a,x});
        }
        int fans = INF;
        for (int cov = -1; cov<m; cov++){
            priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;

            for (int x = 0; x<=n; x++){
                dist[x] = INF;
            }
            dist[1] = 0;
            pq.push({0,1});
            while (!pq.empty()){
                int d = pq.top().first;
                int node = pq.top().second;
                pq.pop();
                if (d>dist[node]) continue;
                for (auto x : adjl[node]){
                    if (x.second==cov) continue;
                    if (dist[node]+c[x.second]<dist[x.first]){
                        dist[x.first] = dist[node]+c[x.second];
                        pq.push({dist[x.first],x.first});
                    }
                }
                for (auto x : rev[node]){
                    if (x.second!=cov) continue;
                    if (dist[node]+c[x.second]<dist[x.first]){
                        dist[x.first] = dist[node]+c[x.second];
                        pq.push({dist[x.first],x.first});
                    }
                }
            }
            int ans = dist[n];
            if (ans==INF) continue;
            for (int x = 0; x<=n; x++){
                dist[x] = INF;
            }
            dist[n] = 0;
            pq.push({0,n});
            while (!pq.empty()){
                int d = pq.top().first;
                int node = pq.top().second;
                pq.pop();
                if (d>dist[node]) continue;
                for (auto x : adjl[node]){
                    if (x.second==cov) continue;
                    if (dist[node]+c[x.second]<dist[x.first]){
                        dist[x.first] = dist[node]+c[x.second];
                        pq.push({dist[x.first],x.first});
                    }
                }
                for (auto x : rev[node]){
                    if (x.second!=cov) continue;
                    if (dist[node]+c[x.second]<dist[x.first]){
                        dist[x.first] = dist[node]+c[x.second];
                        pq.push({dist[x.first],x.first});
                    }
                }
            }
            if (dist[1]==INF) continue;
            fans = min(fans,ans+dist[1]+d[cov]);
        }
        printf("%lld",fans==INF?-1:fans);
    }
}

Compilation message

ho_t4.cpp:14:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~~~~
ho_t4.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:46:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld%lld%lld%lld",&a,&b,&c[x],&d[x]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 1536 KB Output is correct
2 Correct 78 ms 1656 KB Output is correct
3 Correct 77 ms 1760 KB Output is correct
4 Correct 85 ms 1536 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 77 ms 1656 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 1664 KB Output is correct
2 Correct 100 ms 1664 KB Output is correct
3 Correct 100 ms 1648 KB Output is correct
4 Correct 77 ms 1656 KB Output is correct
5 Correct 77 ms 1536 KB Output is correct
6 Correct 76 ms 1536 KB Output is correct
7 Correct 77 ms 1656 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Incorrect 104 ms 1640 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 1652 KB Output is correct
2 Correct 80 ms 1664 KB Output is correct
3 Correct 95 ms 1784 KB Output is correct
4 Correct 76 ms 1656 KB Output is correct
5 Correct 97 ms 1536 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 1536 KB Output is correct
2 Correct 78 ms 1656 KB Output is correct
3 Correct 77 ms 1760 KB Output is correct
4 Correct 85 ms 1536 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 77 ms 1656 KB Output is correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -