Pagini recente » Cod sursa (job #1180164) | Cod sursa (job #1586984) | Cod sursa (job #897260) | Cod sursa (job #945840) | Cod sursa (job #713169)
Cod sursa(job #713169)
#include<fstream>
#include<vector>
#define lung 36001
#define inf 1 << 30
using namespace std;
ifstream fin("catun.in");
ofstream fout("catun.out");
struct nod{int val,cost;
nod *next;
};
nod *v[36001],*q;
int n,m,a,i,poz[lung],h[lung],d[lung],fort[lung],rasp[lung],k,nr;
bool viz[lung];
inline void downheap (int x)
{int fiu;
while (x <= k)
{ fiu = x;
if ((x << 1) <= k)
{ fiu = x << 1;
if (fiu+1 <=k && d[h[fiu+1]] < d[h[fiu]])
++fiu;
}
else
break;
if (d[h[fiu]] < d[h[x]])
{ poz[h[fiu]] = x;
poz[h[x]] = fiu;
h[x] = h[x] + h[fiu] - (h[fiu] = h[x]);
x = fiu;
}
else
break;
}
}
inline void upheap (int x)
{int tata;
while (x > 1)
{ tata = x >> 1;
if (d[h[x]] < d[h[tata]])
{ poz[h[x]] = tata;
poz[h[tata]] = x;
h[x] = h[x] + h[tata] - (h[tata] = h[x]);
x = tata;
}
else
x = 1;
}
}
inline void dijkstra(int aux)
{int minim,i;
for (i=1;i<=n;++i)
{ d[i] = inf;
poz[i] = -1;
}
k=0;
poz[aux] = 1;
h[1] = aux;
d[aux] = 0;
++k;
while (k)
{ if (viz[h[1]])
{ rasp[a] = h[1];
int ind = d[h[1]];
while (k)
{ if (viz[h[k]])
if (ind == d[h[k]] && h[k] < rasp[a])
rasp[a] = h[k];
--k;
}
break;
}
minim = h[1];
h[1] = h[1] + h[k] - (h[k] = h[1]);
poz[h[1]] = 1;
--k;
downheap(1);
q = v[minim];
while (q)
{ if (d[q->val] > d[minim] + q->cost)
{ d[q->val] = d[minim] + q->cost;
if (poz[q->val] != -1)
upheap(poz[q->val]);
else
{ h[++k] = q->val;
poz[h[k]] = k;
upheap(k);
}
}
q = q -> next;
}
}
}
int main()
{int b,c;
fin >> n >> m >> nr;
for (i=1;i<=nr;++i)
{ fin >> a;
viz[a] = true;
}
for (i=1;i<=m;++i)
{ fin >> a >> b >> c;
q = new nod;
q -> val = b;
q -> cost = c;
q -> next = v[a];
v[a] = q;
q = new nod;
q -> val = a;
q -> next = v[b];
q -> cost = c;
v[b] = q;
}
for (a=1;a<=n;++a)
if (!viz[a])
dijkstra(a);
for (a=1;a<=n;++a)
fout << rasp[a] << " ";
return 0;
}