Pagini recente » Cod sursa (job #2973470) | Cod sursa (job #2266809) | Cod sursa (job #2990293) | Cod sursa (job #3193777) | Cod sursa (job #701804)
Cod sursa(job #701804)
#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;
//t[u].push_back(u);
}
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);
v[y].v.push_back(x);
v[y].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\n",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))
if (v[k].v.at(i)!=n or t[k].size()+o[k]==nro)
{
//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 ",t[n].at(i));
//printf("\n");
printf("%d",cost[n]);
return 0;
}