Submission #101868

#	Time	Username	Problem	Language	Result	Execution time	Memory
101868		shafinalam	Cities (BOI16_cities)	C++14	100 / 100	4790 ms	48256 KiB

cities

#include <bits/stdc++.h>

using namespace std;

const int mx = 1e5+5;
typedef long long ll;
typedef pair<ll,ll>pii;

#define  sf scanf
#define  pf printf

#define  inf 1e16
#define  ff first
#define  ss second
#define  MP make_pair
#define  pb push_back

vector<pii>adj[mx];
ll dis[1<<5][mx];
int arr[10];

int main()
{
    int n, k, m;
    sf("%d%d%d", &n, &k, &m);

    for(int i = 1; i < (1<<k); i++)
    {
        for(int r = 1; r <= n; r++) dis[i][r] = inf;
    }
    for(int i = 0; i < k; i++)
    {
        sf("%d", &arr[i]);
        dis[1<<i][arr[i]] = 0;
    }
    while(m--)
    {
        int u, v;
        ll c;
        sf("%d%d%lld", &u, &v, &c);

        adj[u].push_back(make_pair(v, c));
        adj[v].push_back(make_pair(u, c));
    }
    for(int x = 1; x < (1<<k); x++)
    {
        for(int y = 0; y < x; y++)
        {
            if((x|y)==x)
            {
                for(int node = 1; node <= n; node++) dis[x][node] = min(dis[x][node], dis[x^y][node]+dis[y][node]);
            }
        }
        priority_queue<pii, vector<pii>, greater<pii> >pq;
        for(ll node = 1; node <= n; node++)
        {
            if(dis[x][node]<inf) pq.push(make_pair(dis[x][node], node));
        }
        while(!pq.empty())
        {
            pii top = pq.top();
            pq.pop();
            ll u = top.ss;
            ll  cost = top.ff;
            for(int i = 0; i < adj[u].size(); i++)
            {
                ll v = adj[u][i].ff;
                ll  c = adj[u][i].ss;
                if(dis[x][v]>cost+c)
                {
                    dis[x][v] = cost+c;
                    pq.push(make_pair(dis[x][v], v));
                }
            }
        }
    }
    ll ans = inf;
    for(int i = 1; i <= n; i++) ans = min(ans, dis[(1<<k)-1][i]);
    pf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:65:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < adj[u].size(); i++)
                            ~~^~~~~~~~~~~~~~~
cities.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     sf("%d%d%d", &n, &k, &m);
       ^
cities.cpp:33:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         sf("%d", &arr[i]);
           ^
cities.cpp:40:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         sf("%d%d%lld", &u, &v, &c);
           ^

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26