Cod sursa(job #2547734)

Utilizator RedPipperNastasa Stefan-Alexandru RedPipper Data 15 februarie 2020 17:10:27
Problema Ubuntzei Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <bits/stdc++.h>
#define pii pair<int,int>
#define make_pii(a,b) make_pair(a,b)
#define INF -1

using namespace std;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");

const int lmt = 2e3+1;
int n,m,k,sum, ndViz;
bool viz[lmt];
vector<int> ctLst;
vector<pii> aList[lmt];

void citire()
{
    fin>>n>>m>>k;
    ctLst.push_back(1);
    for(int i=1;i<=k;++i)
    {
        int x;
        fin>>x;
        ctLst.push_back(x);
    }
    ctLst.push_back(n);
    for(int i=1;i<=m;++i)
    {
        int x,y,z;
        fin>>x>>y>>z;
        aList[x].push_back(make_pii(y,z));
        aList[y].push_back(make_pii(x,z));
    }
}

int dijkstra(int src)
{
    //rezolva dijkstra
    vector<int> dist(n+1,INF);
    set<pii> bfsq;
    dist[src]=0;
    bfsq.insert(make_pii(0,src));
    while(!bfsq.empty())
    {
        pii crnt = *(bfsq.begin());
        bfsq.erase(*(bfsq.begin()));
        int u = crnt.second;
        vector<pii>::iterator i;
        for(i=aList[u].begin();i!=aList[u].end();++i)
        {
            int v = (*i).first;
            int weight = (*i).second;
            int newDist = dist[u] + weight;

            if(dist[v]==INF || dist[v]>newDist)
            {
                if(dist[v]!=INF)
                    bfsq.erase(bfsq.find(make_pii(dist[v],v)));

                dist[v]=newDist;
                bfsq.insert(make_pii(dist[v],v));
            }
        }
    }
    //cauta nodul de dist minima nevizitat
    //si aduna distanta
    int mini = INT_MAX;
    int minNod=-1;
    vector<int>::iterator i;
    for(i=ctLst.begin();i!=ctLst.end();++i)
    {
        int nod = *i;
        if(!viz[nod] && dist[nod]<mini && nod !=n)
        {
            mini=dist[nod];
            minNod=nod;
        }
    }
    if(minNod==-1)
    {
        minNod=n;
        mini = dist[n];
    }
    sum+=mini;
    viz[minNod]=1;
    return minNod;
}

int main()
{
    citire();
    viz[1]=1;
    int nod = 1;
    while(nod!=n)
    {
        nod = dijkstra(nod);
    }

    fout<<sum;
    return 0;
}