Cod sursa(job #1112124)

Utilizator span7aRazvan span7a Data 19 februarie 2014 14:19:14
Problema Ubuntzei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<fstream>
#define M 2000000000
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
 
struct nod
{
    int inf;
    int c;
    nod * leg;
};
typedef nod* PNod;
PNod L[50001];
int q[800000],cost[50001],n,m,x,y,s,v[15];
void add(int a,int b,int costi)
{
    PNod p=new nod;
    p->inf=b;
    p->c=costi;
    p->leg=L[a];
    L[a]=p;
}
void bellford(int poz)
{	 int i;
	q[1]=poz; 
	for(i=1;i<=n;i++)
            cost[i]=M;
	cost[poz]=0;
     int inc=1,sf=1,ok=0;
    while(inc<=sf&&ok==0)
    {
        for(PNod p=L[q[inc]];p;p=p->leg)
            if(cost[p->inf]>cost[q[inc]]+p->c)
            {
                cost[p->inf]=cost[q[inc]]+p->c;
                sf++;
                q[sf]=p->inf;
                  
 
            }
        inc++;
    }
  
	
 
}
int main()
{
    int a,b,costi,i,k;
    f>>n>>m;
    
	f>>k;
	for(i=1;i<=k;i++)
		f>>v[i];
		for(i=1;i<=m;i++)
      {
           f>>a>>b>>costi;
        add(a,b,costi);add(b,a,costi);
      }
			
	if(k==1)
		{bellford(1);s+=cost[v[1]];bellford(v[1]);s+=cost[n];g<<s;}
	else
		{
			bellford(1);
			
			for(i=1;i<k;i++)
		{	
			s+=cost[v[i]];
			bellford(v[i]);
			
		}
			s+=cost[v[n]];
        g<<s;
		}
 
    
    return 0;
}