Pagini recente » Cod sursa (job #485044) | Cod sursa (job #2230640) | Cod sursa (job #982169) | Clasament autumn2007-runda2 | Cod sursa (job #2000554)
#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;
}