oj.uz

Submission #204423

# Submission time Handle Problem Language Result Execution time Memory
204423 2020-02-25T17:55:04 Z CaroLinda Cities (BOI16_cities) C++14
14 / 100
 321 ms 27192 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 = 1e5+10 ;

using namespace std ;

int N , K , M ;
vector< pair<int,int> > adj[MAXN] ;
ll dist[3][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) ) ;

    }

    for(int i = 0 ; i < K ; i++ )
        dijkstra(i, esp[i] ) ;

    if( K == 2 )
    {
        printf("%lld\n", dist[0][ esp[1] ] ) ;
        return 0 ;
    }

    ll ans = inf ;

    for(int i = 1 ; i <= N; i++ )
    {
        ll resp = dist[0][i] + dist[1][i] + dist[2][i] ;

        ans = min(ans, resp) ;

    }

    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 Correct 7 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Runtime error 9 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 17480 KB Output is correct
2 Correct 310 ms 18556 KB Output is correct
3 Correct 135 ms 10232 KB Output is correct
4 Correct 96 ms 10732 KB Output is correct
5 Correct 263 ms 16612 KB Output is correct
6 Correct 95 ms 10744 KB Output is correct
7 Correct 8 ms 2808 KB Output is correct
8 Correct 8 ms 2808 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 321 ms 27132 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 316 ms 27192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -