Cod sursa(job #1517028)

Utilizator DobosDobos Paul Dobos Data 3 noiembrie 2015 19:53:16
Problema Ubuntzei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("ubuntzei.in");
ofstream fout ("ubuntzei.out");
const int MAX = 2005;
const int BMOD = 50;
const int INF = 1e9;
char buffer[BMOD + 1];
int e = BMOD - 1,D[MAX],v[16],n;
vector < pair < int,int > > G[MAX];
set < pair < int, int > > T;
inline void parsare(int &x)
{
    while(!isdigit(buffer[e])){
        e++;
        if(e == BMOD)
            e = 0,fin.read(buffer,BMOD);
    }
    x = 0;
    while(isdigit(buffer[e])){
        x = x * 10 + (buffer[e] - '0');
        e++;
        if(e == BMOD)
            e = 0,fin.read(buffer,BMOD);
    }
}
inline void luiza()
{
    int nod,cost;
    for(int i = 1; i <= n; i++)
        D[i] = INF;
    D[(*T.begin()).second] = 0;
    while(!T.empty())
    {
        cost = (*T.begin()).first;
        nod = (*T.begin()).second;
        T.erase(*T.begin());
        for(int  i = 0 ; i < G[nod].size(); i ++){
            if(D[G[nod][i].second] > D[nod] + G[nod][i].first){
                D[G[nod][i].second] = D[nod] + G[nod][i].first;
                T.insert({D[G[nod][i].second],G[nod][i].second});
            }
        }
    }
}
int main()
{
    int m,x,y,c,p;
    parsare(n); parsare(m); parsare(p);
    for(int i = 1; i <= p ; i++)
        parsare(v[i]);
    for(int i = 1; i <= m; i++){
        parsare(x); parsare(y); parsare(c);
        G[x].push_back({c,y});
        G[y].push_back({c,x});
    }
    T.insert({0,1});
    luiza();
    int mn,poz;
    long long d = 0;
    for(int i = 1; i <= p; i++){
            mn = 1e9 + 1;
        for(int j = 1; j <= p; j++)
            if(D[v[j]] < mn && v[j] != -1)
                mn = D[v[j]],poz = j;
        v[poz] = -1;
        d = d + mn;
        T.insert({0,poz});
    }
    d = d + D[n];
    fout << d;
    return 0;
}