Cod sursa(job #2000554)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 14 iulie 2017 08:03:02
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <iterator>
#define inf 10000001

using namespace std;

ifstream in("catun.in");
ofstream out("catun.out");

int n, m, k;//date intrare
int fort[36001],tata[36001];
vector <pair <int, int> > vecini[36001];
vector <pair <int, int> > :: iterator it;
priority_queue <pair <int, int> , vector <pair <int, int> >, greater <pair <int, int> > > pq;
int dist[36001];
bool viz[36001];

void dijkstra(int plec,int aux){
  for(int i = 1; i <= n; i++){
    viz[i] = false;
  }
  dist[plec] = 0;
  pq.push({dist[plec],plec});
  while(!pq.empty()){
    int minim = pq.top().second;
    pq.pop();
    if(!viz[minim]){
      viz[minim] = true;
      for(it = vecini[minim].begin(); it != vecini[minim].end(); it++)
        if(dist[it -> first] > dist[minim] + it -> second ){
          dist[it -> first] = dist[minim] + it -> second;
          tata[it -> first] = plec;
          if(viz[it -> first] == false)
            pq.push({dist[it->first], it->first});
        }
    }
  }
}

void citire(){
  in >> n >> m >> k;
  for(int i = 1; i<=n; i++)
    dist[i] = inf;
  for(int i = 1; i <= k; i++){
    in >> fort[i];
    dist[fort[i]] = 0;
  }
  for(int i = 1; i <= m; i++){
    int a, b, c;
    in >> a >> b >> c;
    vecini[a].push_back({b,c});
    vecini[b].push_back({a,c});
  }
  for(int i = 1; i <= k ;i++){
    dijkstra(fort[i],i);
  }
  for(int i = 1; i<=n; i++)
    out << tata[i] <<' ';

}

int main(){
  citire();
  return 0;
}