Pagini recente » Cod sursa (job #1975114) | Cod sursa (job #77859) | Cod sursa (job #908356) | Cod sursa (job #941942) | Cod sursa (job #3033362)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <deque>
#define inf 2147483647
using namespace std;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
int a[2001][2001];
int distante[2001];
int m, n, k;
int vk[2001];
int viz[2001];
int a1, a2, a3;
long long dmin, poz, curr, pozcurr;
struct muchie
{
int x, y, c;
};
muchie much;
vector<muchie> q;
void citire()
{
fin >> n >> m >> k;
for(int i = 1 ; i <= k; i++)
fin >> vk[i];
for(int i = 1; i <= m; i++)
{
fin >> a1 >> a2 >> a3;
much.x = a1;
much.y = a2;
much.c = a3;
q.push_back(much);
much.x = a2;
much.y = a1;
q.push_back(much);
a[a1][a2] = a3;
a[a2][a1] = a3;
}
}
void setare(int start)
{
for(int i = 1 ; i <= n; i++)
distante[i] = inf;
for(int i = 1 ; i <= n; i++)
{
if(a[start][i] != 0)
distante[i] = a[start][i];
}
distante[start] = 0;
}
/*void drum(int start)
{
setare(start);
bool ok = true;
while(ok)
{
ok = false;
for(int i = 1; i <= n; i++)
{
for(int j = 1 ; j <= n; j++)
if(distante[i] + a[i][j] < distante[j] && a[i][j])
{
distante[j] = distante[i] + a[i][j];
ok = true;
}
}
}
}*/
void drum(int start)
{
setare(start);
bool ok = true;
while(ok)
{
ok = false;
for(int i = 0; i < q.size(); i++)
{
if(distante[q[i].x] + q[i].c < distante[q[i].y])
{
distante[q[i].y] = distante[q[i].x] + q[i].c;
ok = true;
}
}
}
}
int rezolvare()
{
poz = 1;
for(int j = 1 ; j <= k; j++)
{
drum(poz);
curr = inf;
for(int i = 1 ; i <= k; i++)
{
if(curr > distante[vk[i]] && vk[i] != poz && vk[i])
{
curr = distante[vk[i]];
pozcurr = i;
}
}
poz = pozcurr;
vk[poz] = 0;
dmin += curr;
}
drum(poz);
dmin += distante[n];
return dmin;
}
int main()
{
citire();
fout << rezolvare();
return 0;
}