Cod sursa(job #701592)

Utilizator nbibestNeagu Bogdan Ioan nbibest Data 1 martie 2012 16:42:19
Problema Ubuntzei Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <iostream>
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

int n,m,i,j,l,x,y,c,p,u,k,kk,nro;
queue<int> a;

struct abc
{
    vector<int> v;
    vector<int> c;
} v[5040];

vector<int> t[2010];

int cost[50001],o[2010];

bool infnoi(int x, int y)
{

    if (t[x].size()>t[y].size())
    return true;
    else
    return false;

}

int main()
{

    freopen("ubuntzei.in","r",stdin);
    freopen("ubuntzei.out","w",stdout);


    scanf("%d %d",&n,&m);

    scanf("%d",&nro);

    for (i=1;i<=nro;i++)
    {
        scanf("%d",&u);
        o[u]=1;
    }

    for (i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        v[x].v.push_back(y);
        v[x].c.push_back(c);
    }



    a.push(1);
   // for (i=1;i<=n;i++)
   // cost[i]=999999999;

cost[1]=0;
    //printf("ajunge");

    while (a.size()>0)
    {
        k=a.front();
        a.pop();
       //printf(" din %d ",k);
        for (i=0;i<v[k].v.size();i++)
        {
            //if (cost[v[k].v.at(i)]==0)
            if (cost[v[k].v.at(i)]==0 or cost[v[k].v.at(i)]>v[k].c.at(i)+cost[k] or infnoi(k,v[k].v.at(i)) or (o[k]==1 and t[v[k].v.at(i)].size()<1))
            {
                //printf("in %d \n",v[k].v.at(i));
                if (v[v[k].v.at(i)].v.size()>0)
                a.push(v[k].v.at(i));

                cost[v[k].v.at(i)]=v[k].c.at(i)+cost[k];

                //for (j=0;j<t[v[k].v.at(i)].size();j++)
                t[v[k].v.at(i)].clear();

                //printf("cate is in %d: %d\n",k,t[k].size());
                for (j=0;j<t[k].size();j++)
                t[v[k].v.at(i)].push_back(t[k].at(j));

                if (o[k]==1)
                {
                    t[v[k].v.at(i)].push_back(k);
                }
            }
        }



    }



    //for (i=0;i<t[n].size();i++)
    //printf("%d \n",t[n].at(i));

    printf("%d ",cost[n]);



    return 0;
}