Cod sursa(job #2536846)

Utilizator nicolaee2Martinescu Nicolae nicolaee2 Data 2 februarie 2020 18:37:36
Problema Ubuntzei Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <iostream>
#include<fstream>
#include<bits/stdc++.h>
using namespace std;

#define NMAX 2005

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

vector<pair<int,int> > ma[NMAX];
int n,m,k;
int v[20];
int oo = (1<<30)-1;
int dis[NMAX];
bool esteHeap[NMAX];

struct compara
{
   bool operator()(int a,int b)
   {
      return dis[a] > dis[b];
   }
};

priority_queue<int,vector<int>,compara> heap;

void citire()
{
   fin>>n>>m>>k;
   for(int i=1;i<=k;i++)
   {
      int x;
      fin>>x;
      v[i] = x;
   }
   for(int i=1;i<=m;i++)
   {
      int x,y,c;
      fin>>x>>y>>c;
      ma[x].push_back(make_pair(y,c));
      ma[y].push_back(make_pair(x,c));
   }

}

void Dijkstra(int start)
{
   for(int i=1;i<=n;i++)
      dis[i] = oo;

   dis[start] = 0;
   esteHeap[start] = true;
   heap.push(start);

   while(!heap.empty())
   {
      int nod = heap.top();
      esteHeap[nod] = false;
      heap.pop();
      for(int i=0;i<ma[nod].size();i++)
      {
         int vecin = ma[nod][i].first;
         int cost = ma[nod][i].second;

         if(dis[vecin] > dis[nod] + cost)
         {
            dis[vecin] = dis[nod] + cost;
            if(!esteHeap[vecin])
            {
               heap.push(vecin);
               esteHeap[vecin] = true;
            }

         }

      }
   }

}


void afisare()
{

}

int main()
{

   citire();
   int sum = 0;
   Dijkstra(1);
   for(int i=1;i<=k;i++)
   {
      sum+=dis[v[i]];
      Dijkstra(v[i]);
   }
   sum+=dis[n];
   fout<<sum;
   return 0;
}