Cod sursa(job #898225)

Utilizator michael9ufoStanescu Mihai michael9ufo Data 28 februarie 2013 09:15:37
Problema Ubuntzei Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

int N, M, K, C[2005], i, j;

vector<pair<int, int> > V[10005];

int DMIN[2005];
bool inQ[2005];

int solve()
{

    queue<int> Q;

    memset(DMIN, 0x3f3f3f3f, sizeof(DMIN));
    memset(inQ, false, sizeof(inQ));

    Q.push(1);
    DMIN[1] = 0;
    inQ[1] = true;

    while(!Q.empty())
    {
        int now = Q.front();
        inQ[now] = false;
        Q.pop();

        for(vector<pair<int, int> >::iterator it=V[now].begin();it!=V[now].end();++it)
            if(DMIN[now] + it->second < DMIN[it->first])
            {
                DMIN[it->first] = DMIN[now] + it->second;

                if(!inQ[it->first])
                {
                    Q.push(it->first);
                    inQ[it->first] = true;
                }

            }

    }

}

int main()
{

    freopen("ubuntzei.in", "r", stdin);
    freopen("ubuntzei.out", "w", stdout);

    cin>>N>>M;

    cin>>K;

    for(i=1;i<=K;++i)
        cin>>C[i];

    for(i=1;i<=M;++i)
    {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);
        V[A].push_back(make_pair(B, C));
    }

    solve();

    int rez = 0;
    for(i=1;i<=K;++i)
        rez += DMIN[C[i]];

    rez += DMIN[N];

    cout<<rez<<"\n";
}