oj.uz

Submission #563114

# Submission time Handle Problem Language Result Execution time Memory
563114 2022-05-16T09:26:48 Z Bobonbush Cities (BOI16_cities) C++17
100 / 100
 2837 ms 45640 KB 
#include <bits/stdc++.h>
#define foreach for
#define in :
using namespace std;
typedef long long ll;

/*
Konichiwa
Konichiwa
Ara ~~ ara

Bob no taisuki - Shinobu Kocho
    * * * * *
  *          *
 *         *
*         *        I love SHINOBU <3 <3 <3
 *         *
  *          *
    * * * * *
*/

/*
_________________________


    Author : Bob15324

_________________________
*/

template<class X , class Y>
    bool Minimize(X & x , Y y)
    {
        if((x == -1 || x > y) &&  (y >= 0))
        {
            x = y;
            return true;
        }
        return false;
    }

template<class X , class Y>
    bool Maximize(X & x , Y y)
    {
        if( x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

/* End of templates. Let's see what do we have here */
const int N = 1e5+1;
const int K = 5;
int n , k , m;
int special[K];
long long dist[N] , dp[N][1 << K];


class GRAPH
{
    private:
        vector<vector<pair<int ,int >>>vertices;

    public:
        GRAPH(int _n)
        {
            vertices.resize(_n+1);
        }

        void AddEdge(int u ,int v ,int w)
        {
            vertices[u].push_back(make_pair(v , w));
            vertices[v].push_back(make_pair(u , w));
        }

        void Dijktra()
        {
            priority_queue<pair<long long , int > , vector<pair<long long , int>> , greater<pair<long long , int>>>pq;
            for(int i = 1; i <= n ; i++)
            {
                pq.push(make_pair(dist[i] , i));
            }
            while(!pq.empty())
            {
                pair<long long , int > temp = pq.top();
                pq.pop();
                int u = temp.second;
                long long du = temp.first;
                if(dist[u] < du)
                {
                    continue;
                }
                foreach(pair<int ,int > adj in vertices[u])
                {
                    int v = adj.first;
                    int w = adj.second;
                    if(Minimize(dist[v] , dist[u] + w))
                    {
                        pq.push(make_pair(dist[v] , v));
                    }
                }
            }
        }
};

int main()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);
    cin >> n >> k >> m;
    for(int i = 1; i <= n ; i++)
    {
        dist[i] = 1e18+1;
        for(int j = 0 ; j <= (1 << k)-1 ; j++)
        {
            dp[i][j] = 1e18+1;
        }
    }
    for(int i = 0;  i< k ; i++)
    {
        cin >> special[i];
        dp[special[i]][1 << i] = 0;
    }
    GRAPH graph(n);
    for(int i = 1; i <= m ; i++)
    {
        int u , v , w;
        cin >> u >> v >> w;
        graph.AddEdge(u , v , w);
    }
    for(int mask = 0 ; mask <= (1 << k )-1 ; mask++)
    {
        for(int i = 0 ; i <= (1 << k)-1 ; i++ )
        {
            for(int j = 0 ; j <= (1 << k)-1 ; j++)
            {
                if((i | j) == mask)
                {
                    for(int z = 1 ; z <= n ; z++)
                    {
                        Minimize(dp[z][mask] , dp[z][i] + dp[z][j]);
                    }
                }
            }
        }

        for(int i = 1 ; i <= n ; i++)
        {
            dist[i] = dp[i][mask];
        }
        graph.Dijktra();
        for(int i = 1 ; i <= n ; i++)
        {
            dp[i][mask] = dist[i];
        }
    }
    long long res = -1;
    for(int i = 1; i <= n ; i++)
    {
        Minimize(res , dp[i][(1 << k)-1]);
    }
    cout << res;
    return 0;
}

//Ehem. My code is amazing. Pay me 2$.Thank you.

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 45524 KB Output is correct
2 Correct 544 ms 45428 KB Output is correct
3 Correct 360 ms 37436 KB Output is correct
4 Correct 59 ms 8760 KB Output is correct
5 Correct 287 ms 45476 KB Output is correct
6 Correct 69 ms 8672 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 2 ms 660 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 728 KB Output is correct
2 Correct 6 ms 728 KB Output is correct
3 Correct 4 ms 660 KB Output is correct
4 Correct 5 ms 596 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1255 ms 45496 KB Output is correct
2 Correct 1126 ms 45580 KB Output is correct
3 Correct 852 ms 37408 KB Output is correct
4 Correct 649 ms 27960 KB Output is correct
5 Correct 159 ms 13300 KB Output is correct
6 Correct 62 ms 10404 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2824 ms 45640 KB Output is correct
2 Correct 2837 ms 45608 KB Output is correct
3 Correct 2713 ms 45480 KB Output is correct
4 Correct 2190 ms 37704 KB Output is correct
5 Correct 1395 ms 28028 KB Output is correct
6 Correct 258 ms 13344 KB Output is correct
7 Correct 72 ms 10396 KB Output is correct