Pagini recente » Cod sursa (job #1879349) | Cod sursa (job #886060) | Cod sursa (job #1715322) | Cod sursa (job #2050450) | Cod sursa (job #1370368)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#define inf 0x7fffffff
using namespace std;
int m,n,k;
unsigned short dmin[2010],nodk[2010],nrk[2010][2010];
struct nod
{
int x;
int c;
void atr(int a,int b)
{
x=a;
c=b;
}
bool operator()(int a, int b)
{
if(nrk[a]!=nrk[b])
return nrk[a]>nrk[b];
else
return dmin[a]>dmin[b];
}
};
vector <nod> v[2010];
priority_queue<int, vector<int>, nod> q;
void citire()
{
freopen("ubuntzei.in","r",stdin);
scanf("%d %d\n%d",&n,&m,&k);
for(int i=0;i<k;i++)
{
int a;
scanf(" %d",&a);
nodk[a]=1;
}
for(int i=0;i<m;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
nod p,q;
p.atr(a,c);
q.atr(b,c);
v[a].push_back(q);
v[b].push_back(p);
}
}
void dijkstra()
{
q.push(1);
for(int i=2;i<=m;i++)
dmin[i]=inf;
while(!q.empty())
{
int t=q.top();
q.pop();
for(int i=0;i<v[t].size();i++)
if((nrk[v[t][i].x]<nrk[t]+nodk[v[t][i].x] && nrk[t]<=k) || (nrk[v[t][i].x]==nrk[t] && dmin[v[t][i].x]>dmin[t]+v[t][i].c))
{
nrk[v[t][i].x]=nrk[t]+nodk[v[t][i].x];
dmin[v[t][i].x]=dmin[t]+v[t][i].c;
if(v[t][i].x!=n)
q.push(v[t][i].x);
}
}
freopen("ubuntzei.out","w",stdout);
printf("%d",dmin[n]);
}
int main()
{
citire();
dijkstra();
return 0;
}