Cod sursa(job #1864949)

Utilizator crisaninaCrisan Ina crisanina Data 1 februarie 2017 09:43:23
Problema Ubuntzei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <limits.h>
#include <fstream>
#define DH 100005

using namespace std;

ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");

int n,m,c[100][100],t[100],d[100],viz[100],u[100];

void dijkstra(int x0)
{
    int i,j,minn,ok,k;
    for(i=1;i<=n;i++)
    {
        d[i]=c[x0][i];
        t[i]=x0;
        viz[i]=0;
    }
    t[x0]=0;
    viz[x0]=1;
    ok=1;
    while(ok)
    {
        minn=INT_MAX;
        for(i=1;i<=n;i++)
            if(!viz[i] && minn>d[i])
            {
                minn=d[i];
                k=i;
            }
        if(minn!=INT_MAX)
        {
            viz[k]=1;
            for(i=1;i<=n;i++)
            {
                if(!viz[i] && d[i]>d[k]+c[k][i])
                {
                    d[i]=d[k]+c[k][i];
                    t[i]=k;
                }
            }
        }
        else
            ok=0;
    }

}

void drum(int x)
{
    if(t[x])
    {
        drum(t[x]);
        g<<", "<<x;
    }
    else
        g<<x;
}

int main()
{
    int n,m,x,y,dist,i,x0=1,j,k;
    f>>n>>m>>k;
    for(i=1;i<=k;i++)
        f>>u[k];
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>dist;
        c[x][y]=dist;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(c[i][j]==0)
                c[i][j]=DH;
    dijkstra(1);
    drum(n);

    return 0;
}