Cod sursa(job #696301)
#include<stdio.h>
#include<vector>
#include<queue>
#include<fstream>
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
typedef vector<pair<int,int> >::iterator it;
#define MaxN 2010
#define MaxK 21
int N,M,K,MAX = 2139123,T[MaxK] = {1},D[MaxK][MaxN],V[MaxK],viz[MaxK];
bool isCoada[MaxN];
vector<pair<int,int> > A[MaxN];
void citire(void)
{
int a,b,c;
f >> N >> M;
f >> K;
for(int i=1;i<=K;i++)
f >> T[i];
for(int i=1;i<=M;i++)
{
f >> a >> b >> c;
A[a].push_back(make_pair(b,c));
A[b].push_back(make_pair(a,c));
}
}
void BellmanFord(int k)
{
queue<int> Q;
for(Q.push(T[k]);!Q.empty();isCoada[Q.front()] = false,Q.pop())
for(it i=A[Q.front()].begin();i<A[Q.front()].end();i++)
if(!D[k][i->first] || D[k][i->first] > D[k][Q.front()] + i->second)
{
D[k][i->first] = D[k][Q.front()]+i->second;
if(!isCoada[i->first])
Q.push(i->first),isCoada[i->first] = true;
}
D[k][T[k]] = 0;
}
void BellmanFordPentruToate(void)
{
for(int i=0;i<=K;i++)
BellmanFord(i);
}
inline void back(int k,int S)
{
if(k == K+1)
{
if(S+D[V[k-1]][N] < MAX)
MAX = S+D[V[k-1]][N];
return ;
}
for(int i=1;i<=K;i++)
if(!viz[i] && S+D[V[k-1]][T[i]] < MAX)
{
V[k] = i;
viz[i] = 1;
back(k+1,S+D[V[k-1]][T[i]]);
viz[i] = 0;
}
}
void AflaMinimul(void)
{
BellmanFordPentruToate();
back(1,0);
}
int main()
{
citire();
AflaMinimul();
g << MAX;
return 0;
}