Cod sursa(job #681326)

Utilizator psycho21rAbabab psycho21r Data 16 februarie 2012 21:52:21
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#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;
}