Submission #310682

#	Time	Username	Problem	Language	Result	Execution time	Memory
310682		MrDomino	Cities (BOI16_cities)	C++14	100 / 100	2782 ms	47868 KiB

cities

#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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26