Cod sursa(job #1107237)

Utilizator StefansebiStefan Sebastian Stefansebi Data 13 februarie 2014 18:56:30
Problema Ubuntzei Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
vector <pair <int, int> > v[2009];
long long n, m, k, a, b, c, loc[2001], lo[2001], dmin[2011], ok, mi, poz, i, viz[2001], p, p1, s, k2, j;
struct cmp {
    bool operator() (int x, int y){
        return dmin[x] > dmin[y];
    }
};
priority_queue <int, vector<int>, cmp> q;

int dijk (int st){
    for (i = 1; i <= n; i++)
        dmin[i] = 99999999;
    dmin[st] = 0;
    q.push(st);
    while (!q.empty()) {
        int nod = q.top();
        q.pop();
          for(i = 0; i < v[nod].size(); i++)
            if (dmin[v[nod][i].first] > dmin[nod] + v[nod][i].second){
                dmin[v[nod][i].first] = dmin[nod] + v[nod][i].second;
                q.push(v[nod][i].first);
            }
    }
    mi = 999999999; poz = 0;
    for (i = 1; i <= n; i++)
        if (mi > dmin[i] and lo[i] == 1){
            mi = dmin[i]; poz = i;
        }
    if (poz == 0)
        poz = n;
    lo[poz] = 0; s = s + dmin[poz];
    return poz;
}

int main() {
    fin >> n >> m;
    fin >> k;
    for (i = 1; i <= k; i++){
        fin >> loc[i]; lo[loc[i]] = 1;
    }
    for (i = 1; i <= m; i++){
        fin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));
    }
    p = dijk(1); //fout << p << " ";
    for (j = 1; j <= k; j++)
        p = dijk(p);
    //for (i = 1; i <= n; i++)
      //  fout << lo[i] << " ";
    fout << s;
    fin.close();
    fout.close();
}