Pagini recente » Cod sursa (job #1519844) | Cod sursa (job #2742775) | Cod sursa (job #794612) | Cod sursa (job #1660840) | Cod sursa (job #694006)
Cod sursa(job #694006)
#include <cstdio>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxN 2005
#define INF 0x3f3f3f3f
int N , M , K;
int cost[maxN][maxN] , minim;
vector <int> C;
void roy_floyd ()
{
for (int k = 0 ; k < N ; ++k)
for (int i = 0 ; i < N ; ++i)
for (int j = 0 ; j < N ; ++j)
{
if (i == j) continue;
if (cost[i][k] == 0 || cost[k][j] == 0) continue;
if (cost[i][k] + cost[k][j] < cost[i][j] || cost[i][j] == 0)
cost[i][j] = cost[i][k] + cost[k][j];
}
}
void solve ()
{
int costcur = cost[0][C.front ()] + cost[C.back ()][N - 1];
for (int i = 0 ; i < (int) C.size () - 1 ; ++i)
costcur += cost[C[i]][C[i + 1]];
if (costcur < minim)
minim = costcur;
}
int main ()
{
freopen ("ubuntzei.in" , "r" , stdin);
freopen ("ubuntzei.out" , "w" , stdout);
scanf ("%d %d" , &N , &M);
scanf ("%d" , &K);
int xx;
for (int i = 1 ; i <= K ; ++i)
{
scanf ("%d" , &xx);
--xx;
C.push_back (xx);
}
int a , b , c;
for (int i = 1 ; i <= M ; ++i)
{
scanf ("%d %d %d" , &a , &b , &c);
--a , --b;
cost[a][b] = c;
cost[b][a] = c;
}
minim = INF;
roy_floyd ();
sort (C.begin () , C.end ());
do { solve (); } while (next_permutation (C.begin () , C.end ()));
if (K > 0)
printf ("%d" , minim);
else printf ("%d" , cost[0][N - 1]);
return 0;
}