oj.uz

답안 #990846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
990846 2024-05-31T13:41:12 Z andrei_iorgulescu Cities (BOI16_cities) C++14
74 / 100
 3234 ms 40096 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

int inf = 1e18;

int n,k,m;
vector<int> imp;
vector<pair<int,int>> g[200005];
int dp[200005][16];
vector<int> d[5];

vector<int> dijkstra(int nod0)
{
    vector<int> dist(n + 1);
    for (int i = 1; i <= n; i++)
        dist[i] = inf;
    priority_queue<pair<int,int>> pq;
    pq.push({0,nod0});
    while (!pq.empty())
    {
        int nod = pq.top().second,cost = -pq.top().first;
        pq.pop();
        if (dist[nod] == inf)
        {
            dist[nod] = cost;
            for (auto vecin : g[nod])
            {
                pq.push({-(vecin.second + cost),vecin.first});
            }
        }
    }
    return dist;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k >> m;
    for (int i = 1; i <= k; i++)
    {
        int x;
        cin >> x;
        imp.push_back(x);
    }
    shuffle(imp.begin(),imp.end(),default_random_engine(676));
    for (int i = 1; i <= m; i++)
    {
        int x,y,z;
        cin >> x >> y >> z;
        g[x].push_back({y,z});
        g[y].push_back({x,z});
    }
    k--;
    for (int i = 0; i <= k; i++)
        d[i] = dijkstra(imp[i]);
    for (int mask = 1; mask < (1 << k); mask++)
    {
        for (int nod = 1; nod <= n; nod++)
        {
            dp[nod][mask] = inf;
            for (int mask2 = 1; mask2 <= mask; mask2++)
            {
                if ((mask & mask2) != mask2)
                    continue;
                int lft = 0;
                for (int bit = 0; bit < k; bit++)
                {
                    if ((1 << bit) & mask2)
                        lft += d[bit][nod];
                }
                dp[nod][mask] = min(dp[nod][mask],dp[nod][mask - mask2] + lft);
            }
        }
        for (int nod = 1; nod <= n; nod++)
        {
            vector<vector<int>> dpp;
            dpp.resize(g[nod].size());
            for (int i = 0; i < g[nod].size(); i++)
                dpp[i].resize((1 << k));
            for (int i = 0; i < g[nod].size(); i++)
                for (int j = 0; j < (1 << k); j++)
                    dpp[i][j] = inf;
            for (int i = 0; i < g[nod].size(); i++)
            {
                if (i == 0)
                {
                    for (int j = 0; j < (1 << k); j++)
                    {
                        if ((j & mask) != j or (j == mask))
                            continue;
                        if (j != 0)
                            dpp[i][j] = dp[g[nod][0].first][j] + g[nod][0].second;
                    }
                }
                else
                {
                    for (int j = 0; j < (1 << k); j++)
                    {
                        if ((j & mask) != j)
                            continue;
                        dpp[i][j] = dpp[i - 1][j];
                        if (j != 0)
                        {
                            for (int jj = 1; jj < (1 << k); jj++)
                            {
                                if ((j & jj) != jj or (jj == mask))
                                    continue;
                                dpp[i][j] = min(dpp[i][j],dpp[i - 1][j - jj] + g[nod][i].second + dp[g[nod][i].first][jj]);
                            }
                        }
                    }
                }
            }
            dp[nod][mask] = min(dp[nod][mask],dpp[(int)g[nod].size() - 1][mask]);
        }
        set<pair<int,int>> s;
        for (int nod = 1; nod <= n; nod++)
            s.insert({dp[nod][mask],nod});
        vector<bool> scos(n + 1);
        while (!s.empty())
        {
            pair<int,int> idk = *s.begin();
            s.erase(idk);
            scos[idk.second] = true;
            for (auto it : g[idk.second])
            {
                if (!scos[it.first])
                {
                    s.erase({dp[it.first][mask],it.first});
                    int new_cost = min(dp[it.first][mask],idk.first + it.second);
                    dp[it.first][mask] = new_cost;
                    s.insert({new_cost,it.first});
                }
            }
        }
    }
    int ans = dp[imp[k]][(1 << k) - 1];
    for (int i = 1; i <= n; i++)
        ans = min(ans,d[k][i] + dp[i][(1 << k) - 1]);
    if (ans < dp[imp[k]][(1 << k) - 1])
        assert(false);
    cout << ans;
    return 0;
}

/*
4 2 6
1 3
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8
*/

/**
as vrea sa imi fac un dp[nod][mask] = presupunand ca am plecat din imp[0] si am drum spre nod, cat imi mai ia ca sa ma conectez cu nod de mask
1.dp[nod][mask] ar putea fi dp[nod][mask2], mask2 inclus in mask cu tranzitia dp[nod][mask2] + sum(dist(nd,nod)) cu nd special in mask - mask2
acum sa presupun ca nu leg nodul nod de cnv in mod direct
2.dp[nod][mask] ar putea fi sum(dp[vec][mask_vec] + cost_edge_nod_vec) cu reuniune(mask_vec) = mask, mask_vec disjuncte (caz pe care iau macar 2 vecini)
3.dp[nod][mask] = cost_edge_nod_vec + dp[vec][mask], pe care ordinea in care calculez e gen dupa dp-uri inainte de a lua cazul asta
Complexitate: O(intra in timp)
**/

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:83:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for (int i = 0; i < g[nod].size(); i++)
      |                             ~~^~~~~~~~~~~~~~~
cities.cpp:85:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for (int i = 0; i < g[nod].size(); i++)
      |                             ~~^~~~~~~~~~~~~~~
cities.cpp:88:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             for (int i = 0; i < g[nod].size(); i++)
      |                             ~~^~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 5208 KB Output is correct
2 Correct 1 ms 5212 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 869 ms 38468 KB Output is correct
2 Correct 756 ms 37684 KB Output is correct
3 Correct 243 ms 33748 KB Output is correct
4 Correct 373 ms 29264 KB Output is correct
5 Correct 319 ms 37596 KB Output is correct
6 Correct 210 ms 30000 KB Output is correct
7 Correct 5 ms 5724 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 5724 KB Output is correct
2 Correct 12 ms 5736 KB Output is correct
3 Correct 5 ms 5468 KB Output is correct
4 Correct 8 ms 5724 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1543 ms 39320 KB Output is correct
2 Correct 1454 ms 38572 KB Output is correct
3 Correct 568 ms 34612 KB Output is correct
4 Correct 1077 ms 25876 KB Output is correct
5 Correct 861 ms 29236 KB Output is correct
6 Correct 657 ms 31540 KB Output is correct

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3231 ms 40036 KB Output is correct
2 Correct 3234 ms 40096 KB Output is correct
3 Correct 3143 ms 39448 KB Output is correct
4 Correct 1254 ms 35156 KB Output is correct
5 Correct 2339 ms 30728 KB Output is correct
6 Incorrect 1710 ms 33948 KB Output isn't correct
7 Halted 0 ms 0 KB -