Cod sursa(job #2260482)

Utilizator DandeacDan Deac Dandeac Data 15 octombrie 2018 01:05:10
Problema Ubuntzei Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

#define inf 0x3f3f3f3f
#define GMAX 2010
using namespace std;
ifstream f ("ubuntzei.in");
ofstream g ("ubuntzei.out");

struct point
{
    int nod;
    int cost;
};
bool operator<(point a,point b)
{
    return a.cost > b.cost;
}
bool friends[GMAX];
vector<pair <int,int> > G[GMAX];
priority_queue <point> pq;

void clearPQ(priority_queue<point> &q)
{
    priority_queue <point> empti;
    swap(q,empti);
}

int dist[GMAX];
int costuri[GMAX];
int v[GMAX];
int main()
{
    int n,m,k;
    f>>n>>m>>k;
    for(int i=1;i<=k;i++)
    {

        f>>v[i];
        friends[v[i]] = true;
    }

    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        G[x].push_back(make_pair(y,z));
        G[y].push_back(make_pair(x,z));
    }

    memset(dist, 0x3f, sizeof(dist));

    int I=0;
    int minDist=inf;
    int minNod=1;
     pq.push({1,0});
     for(int i=1;i<=k;i++)
     {
            memset(dist, 0x3f, sizeof(dist));
            while(!pq.empty())
            {

                int nod = pq.top().nod;
                int cost = pq.top().cost;

                pq.pop();

                if(dist[nod]!= inf)
                    continue;

                dist[nod] = cost;

                if(friends[nod])
                {
                    if(dist[nod]<minDist)
                    {
                        minDist = dist[nod];
                        minNod = nod;
                    }

                }
                for(int i=0;i<G[nod].size();i++)
                {
                    pq.push({G[nod][i].first,G[nod][i].second + cost});
                }
            }

            pq.push({minNod,0});
            I++;
            costuri[I] = minDist;
            friends[minNod] = false;
     }

    int s=0;
    for(int i=1;i<=I;i++)
        s+=costuri[i];
    g<<s+dist[n];


    return 0;
}