Pagini recente » Cod sursa (job #161586) | Cod sursa (job #1449250) | Cod sursa (job #1492338) | Cod sursa (job #1717367) | Cod sursa (job #2706232)
#include <bits/stdc++.h>
#define NMAX 36005
#define BIGNUM 99999999999
using namespace std;
/*********************************************/
/// INPUT / OUTPUT
ifstream f("catun.in");
ofstream g("catun.out");
/*********************************************/
/// GLOBAL DECLARATIONS
int N, M, K, nr, ans[NMAX];
bool fortress[NMAX];
long long sol[NMAX];
struct Node
{
int node, dist, ft;
} heap[2 * NMAX];
vector < Node > adjacency[NMAX];
vector < int > fortresses;
map < int, bool > visited[NMAX];
/*********************************************/
/// FUNCTIONS
void ReadInput();
void Solution();
void Output();
/*********************************************/
///-----------------------------------------------------
inline void ReadInput()
{
f >> N >> M >> K;
for(int i = 1 ; i <= K ; ++ i)
{
int fortressIdx;
f >> fortressIdx;
fortress[fortressIdx] = true;
fortresses.push_back(fortressIdx);
}
for(int i = 1 ; i <= M ; ++ i)
{
int a, b, c;
f >> a >> b >> c;
adjacency[a].push_back({b, c});
adjacency[b].push_back({a, c});
}
}
///-----------------------------------------------------
void AddToHeap(int node, int dist, int ft)
{
nr ++;
heap[nr].node = node;
heap[nr].dist = dist;
heap[nr].ft = ft;
int pos = nr;
while(pos / 2 > 0 && heap[pos / 2].dist > heap[pos].dist)
{
swap(heap[pos], heap[pos / 2]);
pos /= 2;
}
}
///-----------------------------------------------------
void RemoveFromHeap()
{
swap(heap[1], heap[nr]);
nr--;
int pos = 1;
while(2 * pos + 1 <= nr && (heap[pos].dist > heap[2 * pos].dist || heap[pos].dist > heap[2 * pos + 1].dist))
{
if(heap[2 * pos].dist < heap[2 * pos + 1].dist)
{
swap(heap[2 * pos], heap[pos]);
pos *= 2;
}
else
{
swap(heap[pos], heap[2 * pos + 1]);
pos = pos * 2 + 1;
}
}
if(pos == nr / 2 && heap[pos].dist > heap[nr].dist)
swap(heap[pos], heap[nr]);
}
///-----------------------------------------------------
inline void Solution()
{
for(int i = 1 ; i <= N ; ++ i)
sol[i] = BIGNUM;
for(int i = 0 ; i < K ; ++ i)
AddToHeap(fortresses[i], 0, fortresses[i]);
while(nr > 0)
{
int node = heap[1].node;
int dist = heap[1].dist;
int ft = heap[1].ft;
RemoveFromHeap();
if(sol[node] == BIGNUM)
{
sol[node] = dist;
ans[node] = ft;
for(auto it: adjacency[node])
{
if(sol[it.node] == BIGNUM)
AddToHeap(it.node, it.dist + dist, ft);
}
}
}
}
///-----------------------------------------------------
inline void Output()
{
for(int i = 1 ; i <= N ; ++ i)
{
if(fortress[i] || sol[i] == BIGNUM)
g << "0 ";
else
g << ans[i] << " ";
}
}
///-----------------------------------------------------
int main()
{
ReadInput();
Solution();
Output();
return 0;
}