Cod sursa(job #886837)

Utilizator ard_procesoareLupicu ard_procesoare Data 23 februarie 2013 12:34:53
Problema Ubuntzei Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
long long sol;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
#define NMAX 2005
int n,m,k,poz,ck[NMAX],drum[NMAX],next;
bool tb[NMAX];
vector <int> v[NMAX],cost[NMAX];
void read()
{
    fin>>n>>m>>k;
    int a,b,c;
    for(int i=1;i<=k;i++)
    {
        fin>>a;
        ck[++poz]=a;
        tb[a]=true;
    }
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        v[a].push_back(b);
        cost[a].push_back(c);
        v[b].push_back(a);
        cost[b].push_back(c);
    }
}
void tipar()
{
    for(int i=1;i<=n;i++)
        fout<<tb[i]<<" ";
    fout<<endl;
    for(int i=1;i<=poz;i++)
        fout<<ck[i]<<" ";
    fout<<endl;
    for(int i=1;i<=n;i++)
        for(int j=0;j<v[i].size();j++)
            fout<<i<<" "<<v[i][j]<<" "<<cost[i][j]<<"\n";
}
void clear2()
{
    for(int i=1;i<=n;i++)
        drum[i]=0;
}
void fnext()
{
    int dist=999999999,j;
    for(int i=1;i<=poz;i++)
        if(drum[ck[i]]<dist)
        {
            j=i;
            dist=drum[ck[i]];
        }
    sol+=dist;
    next=ck[j];
    ck[j]=ck[poz--];
   // fout<<next<<endl;

}
void bfs()
{
    queue <int> qnod;
    int nod;
    qnod.push(next);
    while(!qnod.empty())
    {
        nod=qnod.front();
        qnod.pop();
        for(int i=0;i<v[nod].size();i++)
        {
            if(v[nod][i] == next) continue;
            if(drum[v[nod][i]] == 0 || drum[v[nod][i]] > drum[nod]+cost[nod][i])
            {
                drum[v[nod][i]] = drum[nod]+cost[nod][i];
                qnod.push(v[nod][i]);
            }
        }
    }
}
void tipar_drum()
{
    for(int i=1;i<=n;i++)
        fout<<drum[i]<<" ";
    fout<<endl;
}
int main()
{
    read();
    //tipar();
    next = 1;
    while(poz)
    {
        bfs();
        fnext();
       // tipar_drum();
        clear2();
    }
    bfs();
    sol+=drum[n];
    fout<<sol;//<<"*"<<endl;
   // tipar_drum();
}