Pagini recente » Cod sursa (job #1738163) | Cod sursa (job #295912) | Cod sursa (job #2751672) | Cod sursa (job #2113248) | Cod sursa (job #1654848)
#include <fstream>
#include <stdlib.h>
#include <set>
#define mp make_pair
#define pb push_back
#define INF 1000000000
using namespace std;
ifstream fin("catun.in");
ofstream fout("catun.out");
struct lista{int val, cost;};
int n, m, f, i, F[36005], x, y, c, d[36005], minim, ord;
lista *A[36005];
set < pair <int, int> > heap; // val si idx
void DJ(int x)
{
int val, id, i;
lista p;
for (i=1; i<=n; i++)
d[i]=INF;
d[x]=0;
heap.insert(mp(0, x));
while (heap.size() > 0)
{
val = (*heap.begin()).first;
id = (*heap.begin()).second;
heap.erase(*heap.begin());
for (i=1; i<=A[id][0].val; i++)
{
p=A[id][i];
if (d[p.val] > p.cost + val)
{
d[p.val]=p.cost+val;
heap.insert(mp(d[p.val], p.val));
}
}
}
}
int main()
{
int j;
fin>>n>>m>>f;
for (i=1; i<=f; i++)
{
fin>>x;
F[x]=1;
}
for (i=1; i<=n; i++)
{
A[i] = (lista *) realloc(A[i], 2*sizeof(int));
A[i][0].val=0;
}
for (i=1; i<=m; i++)
{
fin>>x>>y>>c;
A[x][0].val++;
A[x] = (lista *) realloc(A[x], (A[x][0].val+1)*2*sizeof(int));
A[x][A[x][0].val].val=y;
A[x][A[x][0].val].cost=c;
A[y][0].val++;
A[y] = (lista *) realloc(A[y], (A[y][0].val+1)*2*sizeof(int));
A[y][A[y][0].val].val=x;
A[y][A[y][0].val].cost=c;
}
for (i=1; i<=n; i++)
{
if (F[i]==0)
{
DJ(i);
minim=INF;
ord=0;
for (j=1; j<=n; j++)
{
if (F[j]==1 && d[j]<minim)
{
minim=d[j];
ord=j;
}
}
if (minim==INF)
fout<<0<<" ";
else
fout<<ord<<" ";
}
else
fout<<0<<" ";
}
return 0;
}