Cod sursa(job #1648546)

Utilizator dyianTorok Tibor-Daniel dyian Data 11 martie 2016 10:40:52
Problema Ubuntzei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");

int a[2000][2000];
int t[2000],loc[2000],d[2000],h[2000];
int n,m,k,c=0;

void cit()
{
    f>>n>>m>>k;
    if(k!=0)
    for(int i=1;i<=k;i++)
        f>>loc[i];

    int x,y,z;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j) a[i][j] = 0;
                else a[i][j] = 10000;

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

void dijkstra()
{
    int ok=1,k,v[2000],mn;
    for(int i = 1; i <= n; i++)
    {
        v[i] = 0;
        t[i] = 1;
        d[i] = a[1][i];
    }
    v[1] = 1;
    t[1] = 0;
    while(ok == 1)
    {
        mn = 10000;
        for(int i = 1; i <= n; i++)
            if(v[i]==0 and mn > d[i])
            {
                mn = d[i];
                k  = i;
            }

        if(mn != 10000)
        {
            v[k] = 1;
            h[++c] = k;
            for(int i=1;i<=n;i++)
                if(v[i] == 0 and d[i] > d[k] + a[k][i])
                {
                    t[i] = k;
                    d[i] = d[k] + a[k][i];
                }
        }
        else ok = 0;
    }
}

int main()
{
    cit();
    h[1] = 1;
    c++;
    dijkstra();v[1] = 1;
    int s=0;
    for(int i=1;i<=n;i++)
        s += d[i];
    g<<s-1;
}