Pagini recente » Cod sursa (job #339649) | Cod sursa (job #2652024) | Cod sursa (job #28251) | Cod sursa (job #1072130) | Cod sursa (job #681326)
Cod sursa(job #681326)
#include <fstream>
#include <set>
#include <vector>
#include <utility>
#define INF 0x7fffffff
using namespace std;
typedef pair <int, int> edge;
int main()
{
int N, M, K;
ifstream in("catun.in");
in >> N >> M >> K;
pair <bool, vector <edge> > graph[36001];
int dis[36001];
int fort[36001], min[36001];
set< pair<int, int> > S;
for(int i = 1; i <= N; ++i)
{
min[i] = INF;
dis[i] = INF;
}
while(K--)
{
int w;
in >> w;
graph[w].first = true;
S.insert(make_pair(0,w));
dis[w] = 0;
fort[w] = w;
}
for(int i = 0, a, b, c; i < M; ++i)
{
in >> a >> b >> c;
graph[a].second.push_back(make_pair(c,b));
graph[b].second.push_back(make_pair(c,a));
}
in.close();
while (!S.empty())
{
int no = (*S.begin()).second;
int diw = (*S.begin()).first;
S.erase(*S.begin());
for(int i = 0; i < graph[no].second.size(); ++i)
{
if(graph[no].second[i].first + dis[no] < dis[graph[no].second[i].second])
{
fort[graph[no].second[i].second] = fort[no];
dis[graph[no].second[i].second] = graph[no].second[i].first + dis[no];
S.insert(make_pair(dis[graph[no].second[i].second], graph[no].second[i].second));
}
}
}
ofstream out("catun.out");
for(int i = 1; i <= N; ++i)
{
if(graph[i].first)
{
out << "0 ";
continue;
}
out << fort[i] << " ";
}
out.close();
return 0;
}