Cod sursa(job #2205738)

Utilizator EclipseTepes Alexandru Eclipse Data 20 mai 2018 03:30:02
Problema Ubuntzei Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#define dMAX 2000
#define INF 999999

using namespace std;

int n, m, k;
int x, y, c;
vector<pair<int, int> > graf[dMAX + 2];
vector<int> prieteni;
bool pr[dMAX + 2];

deque<int> myDeque;
int pVerif, newV;
int currentV, mini, idx;
int d[dMAX + 2], L;
bool taken[dMAX + 2], found;

ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");

int main()
{
    int i, j;
    fin >> n >> m;
    fin >> k;
    for (i = 1; i <= k; i++) {
        fin >> x;
        prieteni.push_back(x);
        pr[x] = true;
    }
    for (i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        graf[x].push_back({y, c});
        graf[y].push_back({x, c});
    }
    currentV = 1;
    taken[currentV] = true;
    while (currentV != n) {
        for (j = 1; j <= n; j++) d[j] = INF;
        mini = INF + 2;
        d[currentV] = 0;

        myDeque.push_back(currentV);
        while (!myDeque.empty()) {
            pVerif = myDeque.front();
            myDeque.pop_front();
            for (i = 0; i < graf[pVerif].size(); i++) {
                newV = graf[pVerif][i].first;
                c = graf[pVerif][i].second;
                if (d[newV] > d[pVerif] + c) {
                    d[newV] = d[pVerif] + c;
                    myDeque.push_back(newV);
                }
            }
        }
        currentV = n;
        for (j = 1; j <= n; j++) {
            if (!taken[j]) {
                if (pr[j]) {
                    if (mini > d[j]) {
                        mini = d[j];
                        currentV = j;
                    }
                }
            }
        }
        L += d[currentV];
        taken[currentV] = true;
    }
    fout << L;

    return 0;
}