Cod sursa(job #2149065)

Utilizator cosceexcosceex cosceex Data 2 martie 2018 11:56:36
Problema Ubuntzei Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <bits/stdc++.h>
#define oo 100005
using namespace std;

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

int n,m,k;
int x,y,z,v[20];
int a[2001][2001];
int d[20001],t[20001],p[20001];

void dijkstra(int s)
{ int i,j,k,min;
  for(i=1;i<=n;i++)
     { d[i]=a[s][i];
       if(i!=s && d[i]!=oo) t[i]=s;
     }
  p[s]=1;
  for(k=1;k<n;k++)
   { min=oo;
     for(i=1;i<=n;i++)
       if(!p[i] && d[i]<min) { min=d[i]; j=i;
			     }
     for(i=1;i<=n;i++)
       if(!p[i])
       if(d[i]>d[j]+a[j][i])
	 { d[i]=d[j]+a[j][i];
	   t[i]=j;
	 }
     p[j]=1;
   }
}

void drum(int i)
{ if(t[i]) drum(t[i]);
  g<<i<<" ";
}

int main()
{
    f>>n>>m;
    f>>k;
    for(int i=1;i<=k;i++)
        f>>v[i];
    //for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
           d[j]=oo;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=oo;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        a[x][y]=a[y][z]=z;
    }
    //d[1]=0;
    dijkstra(1);

   /* for(int i=1;i<=n;i++)
        {for(int j=1;j<=n;j++)
            if(a[i][j]!=oo)
            g<<a[i][j]<<" ";
            else g<<"0 ";
            g<<'\n';
        } */
        //g<<'\n';g<<'\n';g<<'\n';
       /*for(int i=1;i<=n;i++)
    if(i!=1)
    {g<<1<<"->"<<i<<": ";
     drum(i);
     g<<"="<<d[i]<<endl;
    }*/

    if(k==0)
        g<<d[n];
    else
    {
        int s=0;
        s+=d[v[1]];
        for(int i=2;i<=k;i++)
        {
            dijkstra(v[i]);
            s+=d[v[i]];
        }
        g<<s+d[n];
    }
    return 0;
}