Pagini recente » Cod sursa (job #1811371) | Cod sursa (job #2125221) | Cod sursa (job #663912) | Cod sursa (job #2727249) | Cod sursa (job #588927)
Cod sursa(job #588927)
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#define inf 2147000000
using namespace std;
struct s_node
{
vector <int> id;
vector <int> wg;
int val;
int ap_feud;
};
int n,m,k,feud[36000];
s_node node[36001];
queue <int> q;
int main()
{
ifstream in("catun.in");
ofstream out("catun.out");
int x,y,z;
int i1,i2,i3;
vector <int>::iterator it1,it2;
//citire
in>>n>>m>>k;
for(i1=0;i1<k;i1++)
in>>feud[i1];
sort(feud,feud+k);
for(i1=0;i1<m;i1++)
{
in>>x>>y>>z;
node[x].id.push_back(y);
node[x].wg.push_back(z);
node[y].id.push_back(x);
node[y].wg.push_back(z);
}
//
//initializare
for(i1=1;i1<=n;i1++)
{
node[i1].val = inf;
}
//
//dijkstra
bool sw;
for(i3=0;i3<k;i3++) //pentru fiecare feuda(nod)
{
q.push(feud[i3]);
node[feud[i3]].val = 0;
while(!q.empty())
{
for(it1 = node[q.front()].id.begin(), it2 = node[q.front()].wg.begin(); //pentru fiecare nod adiacent
it1!=node[q.front()].id.end();
it1++,it2++)
{
sw = false;
if(node[*it1].val > node[q.front()].val + *it2)
sw = true;
if(sw)
{
node[*it1].val = node[q.front()].val + *it2;
node[*it1].ap_feud = feud[i3];
q.push(*it1);
}
}
q.pop();
}
}
//
//afisare
for(i1=0;i1<k;i1++)
node[feud[i1]].ap_feud = 0;
for(i1=1;i1<=n;i1++)
out<<node[i1].ap_feud<<' ';
//
in.close();
out.close();
return 0;
}