Pagini recente » Cod sursa (job #2559300) | Cod sursa (job #2509092) | Cod sursa (job #2341044) | Cod sursa (job #2576905) | Cod sursa (job #701592)
Cod sursa(job #701592)
#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;
}