oj.uz

Submission #310682

# Submission time Handle Problem Language Result Execution time Memory
310682 2020-10-07T15:49:28 Z MrDomino Cities (BOI16_cities) C++14
100 / 100
 2782 ms 47868 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=(int) 1e5;
const int K=5;
const ll INF=(ll) 1e18;
int n,k,m;

struct E
{
        int x;
        ll cost;
};

vector<E> g[N];
ll dp[1<<K][N];

int main()
{
        ios::sync_with_stdio(0);
        cin.tie(0);

        /** Azi am terminat de citit "Enigma Otiliei" de G Calinescu -> nu-mi place finalul. **/

        cin>>n>>k>>m;
        for (int i=1;i<(1<<k);i++)
                for (int j=0;j<n;j++)
                        dp[i][j]=INF;
        for (int i=0;i<k;i++)
        {
                int c;
                cin>>c;
                c--;
                dp[1<<i][c]=0;
        }
        for (int i=0;i<m;i++)
        {
                int x,y,c;
                cin>>x>>y>>c;
                x--;
                y--;
                g[x].push_back({y,c});
                g[y].push_back({x,c});
        }
        for (int m=1;m<(1<<k);m++)
        {
                for (int m2=0;m2<=m;m2++)
                {
                        int m3=m-m2;
                        if ((m2&m3)==0)
                                for (int i=0;i<n;i++)
                                        dp[m][i]=min(dp[m][i],dp[m2][i]+dp[m3][i]);
                }
                priority_queue<pair<ll,int>> pq;
                for (int i=0;i<n;i++)
                        pq.push(make_pair(-dp[m][i],i));
                while (!pq.empty())
                {
                        int i=pq.top().second;
                        ll val=pq.top().first;
                        pq.pop();
                        if (val!=-dp[m][i])
                                continue;
                        for (auto &it : g[i])
                        {
                                int j=it.x;
                                ll val=dp[m][i]+it.cost;
                                if (val<dp[m][j])
                                {
                                        dp[m][j]=val;
                                        pq.push({-dp[m][j],j});
                                }
                        }
                }
        }
        ll sol=INF;
        for (int i=0;i<n;i++)
                sol=min(sol,dp[(1<<k)-1][i]);
        cout<<sol<<"\n";
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 25248 KB Output is correct
2 Correct 670 ms 24660 KB Output is correct
3 Correct 427 ms 17096 KB Output is correct
4 Correct 74 ms 11724 KB Output is correct
5 Correct 379 ms 21864 KB Output is correct
6 Correct 70 ms 11688 KB Output is correct
7 Correct 5 ms 2944 KB Output is correct
8 Correct 4 ms 2944 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1310 ms 31440 KB Output is correct
2 Correct 1306 ms 31072 KB Output is correct
3 Correct 858 ms 23440 KB Output is correct
4 Correct 725 ms 22668 KB Output is correct
5 Correct 192 ms 14552 KB Output is correct
6 Correct 82 ms 14160 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2633 ms 44372 KB Output is correct
2 Correct 2675 ms 47868 KB Output is correct
3 Correct 2782 ms 47592 KB Output is correct
4 Correct 1843 ms 38264 KB Output is correct
5 Correct 1361 ms 33060 KB Output is correct
6 Correct 300 ms 19732 KB Output is correct
7 Correct 102 ms 17544 KB Output is correct