oj.uz

Submission #101868

# Submission time Handle Problem Language Result Execution time Memory
101868 2019-03-20T15:22:38 Z shafinalam Cities (BOI16_cities) C++14
100 / 100
 4790 ms 48256 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1127 ms 24972 KB Output is correct
2 Correct 1197 ms 28844 KB Output is correct
3 Correct 714 ms 19364 KB Output is correct
4 Correct 146 ms 15332 KB Output is correct
5 Correct 591 ms 23972 KB Output is correct
6 Correct 128 ms 15160 KB Output is correct
7 Correct 8 ms 2944 KB Output is correct
8 Correct 8 ms 3072 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3072 KB Output is correct
2 Correct 10 ms 3072 KB Output is correct
3 Correct 8 ms 2944 KB Output is correct
4 Correct 10 ms 3072 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2205 ms 31388 KB Output is correct
2 Correct 2221 ms 34992 KB Output is correct
3 Correct 1508 ms 25584 KB Output is correct
4 Correct 1204 ms 27012 KB Output is correct
5 Correct 393 ms 17752 KB Output is correct
6 Correct 162 ms 17528 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4265 ms 44104 KB Output is correct
2 Correct 4790 ms 48256 KB Output is correct
3 Correct 4424 ms 47728 KB Output is correct
4 Correct 2973 ms 38232 KB Output is correct
5 Correct 2065 ms 33204 KB Output is correct
6 Correct 555 ms 19140 KB Output is correct
7 Correct 194 ms 17528 KB Output is correct