Submission #204423

#	Time	Username	Problem	Language	Result	Execution time	Memory
204423		CaroLinda	Cities (BOI16_cities)	C++14	14 / 100	321 ms	27192 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 = 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 (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: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26