Cod sursa(job #2579870)

Utilizator AlexandruBrezuleanuAlexandruBrezuleanu AlexandruBrezuleanu Data 12 martie 2020 22:42:07
Problema Ubuntzei Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <bits/stdc++.h>
#define MAX 2200
#define MAX2 20
#define INF 2000000000
#define PUTERE 280000
using namespace std;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
struct nod
{
    int x,cost;
};
int v[MAX2];
vector<nod>g[MAX];
int d[MAX],cat[MAX2][MAX];
bool uz[MAX];
int dp[PUTERE][MAX2];
inline bool operator <(nod a,nod b)
{
    return a.cost>b.cost;
}
priority_queue<nod>pq;
void dijkstra(int node);
int n,m,k,mini;
int main()
{
    int node,vecin,mask,mask2,i,x,y,z,j;
    fin>>n>>m;
    fin>>k;
    for(i=0; i<k; i++)
        fin>>v[i];
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>z;
        g[x].push_back({y,z});
        g[y].push_back({x,z});
    }
    if(k>0)
    {for(i=0; i<k; i++)
        dijkstra(i);
    for(i=0; i<(1<<k); i++)
        for(j=0; j<k; j++)
            dp[i][j]=INF;
    for(i=0; i<k; i++)
        dp[(1<<i)][i]=cat[i][1];
    for(mask=0; mask<(1<<k); mask++)
        for(node=0; node<k; node++)
            if(mask&(1<<node))
            {
                mask2=mask^(1<<node);
                for(vecin=0; vecin<k; vecin++)
                    if(mask2&(1<<vecin))
                        dp[mask][node]=min(dp[mask][node],dp[mask2][vecin] + cat[node][v[vecin]]);
            }
    mini=INF;
    for(node=0; node<k; node++)
        mini=min(mini,dp[(1<<k)-1][node]+cat[node][n]);
    fout<<mini;
    }
    else
    {
        v[0]=1;
        dijkstra(0);
        fout<<cat[0][n];
    }
    return 0;
}
void dijkstra(int node)
{

    int i,nodcrt,start=node;
    node=v[node];
    for(i=0; i<MAX; i++)
        uz[i]=0,d[i]=INF;
    d[node]=0;
    pq.push({node,d[node]});
    uz[node]=1;
    while(!pq.empty())
    {
        nodcrt=pq.top().x;
        pq.pop();
        uz[nodcrt]=0;
        for(auto &it:g[nodcrt])
        {
            if(d[it.x]>d[nodcrt]+it.cost)
            {
                d[it.x]=d[nodcrt]+it.cost;
                if(!uz[it.x])
                {
                    pq.push({it.x,d[it.x]});
                    uz[it.x]=1;
                }
            }
        }
    }
    for(i=1; i<=n; i++)
        cat[start][i]=d[i];
}