Cod sursa(job #1105689)

Utilizator GoldEagleAndrei Iulian GoldEagle Data 11 februarie 2014 23:35:56
Problema Ubuntzei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
/*
 * Created on: February 5th 2014
 * Author: <Marin Andrei>
 * Description: problema 2 oji 2011. clasele 11-12;
 */

 #include <iostream>
 #include <fstream>
 using namespace std;

 fstream f ("ubuntzei.in",ios::in);
 fstream g ("ubuntzei.out",ios::out);

 int viz[100];

 int main (void)
 {
     int n,m,k,z,i,j,cost,NC=1,x,y,h,mini,NV;
     long a[100][100],CT;
     f>>n>>m;
     f>>k;
     for (i=1;i<=k;i++)
        {f>>z;
        viz[z]=1;}
    //initializarea matricei
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
        a[i][j]=100001;

    for (i=1;i<=m;++i)
    {
        f>>x>>y>>z;
        a[x][y]=a[y][x]=z;
    }

    /*for (i=1;i<=n;++i)
    {
        for (j=1;j<=n;++j)
        //cout<<a[i][j]<<" ";
        //cout<<endl;
    }
    */

    //aplicarea algoritm roy-floyd
    for (h=1;h<=n;++h)
        for (i=1;i<=n;++i)
            for (j=1;j<=n;++j)
            if (a[i][h]+a[h][j] < a[i][j])
            a[i][j]=a[j][i]=a[i][h]+a[h][j];

    CT=0;
    NC=1;
    for (h=1;h<=k;++h)
    {
        mini=100001;
    for (i=1;i<=n;++i)
        if (viz[i] && a[NC][i] < mini)
    {
        mini=a[NC][i];
        NV=i;
    }
    /*for (i=1;i<=n;++i)
    {for (j=1;j<=n;++j)
        //cout<<a[i][j]<<" ";
        //cout<<endl;}
        */

    CT+=a[NC][NV];
    //cout<<CT<<" ";
    NC=NV;
    viz[NV]=0;
    }
     CT+=a[NC][n];
     //cout<<CT;
     g<<CT;
     f.close();
     g.close();
     return 0;
 }