Submission #204429

#	Time	Username	Problem	Language	Result	Execution time	Memory
204429		CaroLinda	Cities (BOI16_cities)	C++14	15 / 100	197 ms	8312 KiB

cities

#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 (stderr)

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
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26