Cod sursa(job #1227706)

Utilizator TudorMTudor Moldovanu TudorM Data 11 septembrie 2014 14:27:29
Problema Ubuntzei Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<fstream>
#include<queue>
#define INF 1000000
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int s, n, m, k, nr, d[1001], v[1001][1001];
bool prieten[1001];
queue <int> c;
void citire()
{
    int i, j, x, y, pret;
    f>>n>>m>>k;
    for(i=1;i<=k;i++)
    {
        f>>x;
        prieten[x]=1;
    }
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>pret;
        v[x][y]=v[y][x]=pret;
    }
}
void bmf(int x)
{
    int i, u, p, ok1, poz;
    for(i=1;i<=n;i++)d[i]=INF;
    d[x]=0;
    c.push(x);
    while(!c.empty())
    {
        ok1=0;
        p=c.front();
        for(i=1;i<=n;i++)
        {
            if(d[i]>d[p]+v[p][i]&&v[p][i])
            {
                ok1=1;
                d[i]=d[p]+v[p][i];
                c.push(i);
            }
        }
        if(!ok1)c.pop();
    }
}
int main()
{
    int i, j, ultim, mini=INF, poz;
    citire();
    int nr=k;
    bmf(1);
    for(i=2;i<=n;i++)
    {
        if(d[i]<mini&&(prieten[i]||(k==0&&i==n)))
        {
            mini=d[i];
            ultim=i;
        }
    }
    if(nr)nr--;
    prieten[ultim]=0;
    s+=d[ultim];
    while(nr)
    {
        bmf(ultim);
        mini=INF;
        for(i=1;i<=n;i++)
        {
            if(d[i]<mini&&prieten[i]&&i!=ultim)
            {
                mini=d[i];
                poz=i;
            }
        }
        s+=d[poz];
        ultim=poz;
        nr--;
    }
    bmf(ultim);
    s+=d[n];
    g<<s;
    f.close();
    g.close();
    return 0;
}