Submission #101865

#	Time	Username	Problem	Language	Result	Execution time	Memory
101865		shafinalam	Cities (BOI16_cities)	C++14	0 / 100	3770 ms	48276 KiB

cities

#include <bits/stdc++.h>

using namespace std;

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

#define  sf scanf
#define  pf printf

#define  input freopen("input.txt","r",stdin)
#define  output freopen("output.txt","w",stdout)

#define  inf 1e16
#define  ff first
#define  ss second
#define  MP make_pair
#define  pb push_back
#define  all(v) v.begin(), v.end()
#define  printcase(cases) printf("Case %d:", cases);
#define  Unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define  FAST  ios_base::sync_with_stdio(0);cout.tie(0)
#define  endl printf("\n")
#define  __lcm(a, b) ((a*b)/__gcd(a, b))

int  Set(int N,int pos){return N=N | (1<<pos);}
int  reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}

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(int 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();
            int u = top.ss;
            ll  cost = top.ff;
            for(int i = 0; i < adj[u].size(); i++)
            {
                int 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:80:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < adj[u].size(); i++)
                            ~~^~~~~~~~~~~~~~~
cities.cpp:41: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:49:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         sf("%d", &arr[i]);
           ^
cities.cpp:56: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: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26