oj.uz

Submission #204429

# Submission time Handle Problem Language Result Execution time Memory
204429 2020-02-25T18:06:06 Z CaroLinda Cities (BOI16_cities) C++14
15 / 100
 197 ms 8312 KB 
#include <bits/stdc++.h>

#define ll long long
#define debug printf
#define all(x) x.begin(),x.end()

const ll inf = 1e18+10 ;
const int MAXN = 1010;

using namespace std ;

int N , K , M ;
vector< pair<int,int> > adj[MAXN] ;
ll dist[MAXN][MAXN] ;
vector<int> esp ;

inline void dijkstra(int idx, int S)
{
    for(int i = 1 ; i <= N ; i++ ) dist[idx][i] = inf ;
    dist[idx][S] = 0 ;

    priority_queue< pair<ll,int> , vector< pair<ll,int> > , greater< pair<ll,int> > > fila ;

    fila.push( make_pair(0,S) ) ;

    while(!fila.empty() )
    {

        ll d = fila.top().first ;
        int curr = fila.top().second ;

        fila.pop() ;

        if( d != dist[idx][curr] ) continue ;

        for(auto p : adj[curr] )
        {
            int W = p.second ;
            int viz = p.first ;

            if( dist[idx][viz] <= d + W ) continue ;

            dist[idx][viz] = d + W ;
            fila.push( make_pair( d+W, viz )  ) ;
        }

    }

}

int main()
{

    scanf("%d%d%d", &N , &K , &M ) ;
    for(int i = 0 ; i < K ; i++ )
    {
        int x ;
        scanf("%d", &x ) ;

        esp.push_back(x) ;

    }
    for(int i = 0 ; i < M ; i++ )
    {
        int U , V , W ;

        scanf("%d%d%d", &U , &V, &W ) ;

        adj[U].push_back( make_pair(V,W) ) ;
        adj[V].push_back( make_pair(U,W) ) ;

    }

    if( K != 4 ) return 0 ;

    for(int i = 1 ; i <= N ; i++ ) dijkstra(i,i) ;

    ll ans = inf ;

    for(int i = 1 ; i <= N ; i++ )
        for(int j = 1 ; j <= N ; j++ )
        {
            ll caso1 = dist[i][ esp[0] ] + dist[i][ esp[1] ] + dist[j][ esp[2] ] + dist[j][ esp[3] ] ;
            ll caso2 = dist[i][ esp[0] ] + dist[i][ esp[2] ] + dist[j][ esp[3] ] + dist[j][ esp[1] ] ;
            ll caso3 = dist[i][ esp[0] ] + dist[ i ][ esp[3] ] + dist[j][esp[1]] + dist[j][ esp[2] ] ;

            ll resp = min( caso1, min(caso2,caso3) ) ;

            ans = min( ans, resp + dist[i][j] ) ;

        }


    printf("%lld\n" , ans ) ;

}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N , &K , &M ) ;
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x ) ;
         ~~~~~^~~~~~~~~~~
cities.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &U , &V, &W ) ;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 8312 KB Output is correct
2 Correct 189 ms 8312 KB Output is correct
3 Correct 75 ms 8312 KB Output is correct
4 Correct 68 ms 4344 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -