Pagini recente » Cod sursa (job #90154) | Cod sursa (job #2480498) | Cod sursa (job #1164662) | Cod sursa (job #407001) | Cod sursa (job #886837)
Cod sursa(job #886837)
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
long long sol;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
#define NMAX 2005
int n,m,k,poz,ck[NMAX],drum[NMAX],next;
bool tb[NMAX];
vector <int> v[NMAX],cost[NMAX];
void read()
{
fin>>n>>m>>k;
int a,b,c;
for(int i=1;i<=k;i++)
{
fin>>a;
ck[++poz]=a;
tb[a]=true;
}
for(int i=1;i<=m;i++)
{
fin>>a>>b>>c;
v[a].push_back(b);
cost[a].push_back(c);
v[b].push_back(a);
cost[b].push_back(c);
}
}
void tipar()
{
for(int i=1;i<=n;i++)
fout<<tb[i]<<" ";
fout<<endl;
for(int i=1;i<=poz;i++)
fout<<ck[i]<<" ";
fout<<endl;
for(int i=1;i<=n;i++)
for(int j=0;j<v[i].size();j++)
fout<<i<<" "<<v[i][j]<<" "<<cost[i][j]<<"\n";
}
void clear2()
{
for(int i=1;i<=n;i++)
drum[i]=0;
}
void fnext()
{
int dist=999999999,j;
for(int i=1;i<=poz;i++)
if(drum[ck[i]]<dist)
{
j=i;
dist=drum[ck[i]];
}
sol+=dist;
next=ck[j];
ck[j]=ck[poz--];
// fout<<next<<endl;
}
void bfs()
{
queue <int> qnod;
int nod;
qnod.push(next);
while(!qnod.empty())
{
nod=qnod.front();
qnod.pop();
for(int i=0;i<v[nod].size();i++)
{
if(v[nod][i] == next) continue;
if(drum[v[nod][i]] == 0 || drum[v[nod][i]] > drum[nod]+cost[nod][i])
{
drum[v[nod][i]] = drum[nod]+cost[nod][i];
qnod.push(v[nod][i]);
}
}
}
}
void tipar_drum()
{
for(int i=1;i<=n;i++)
fout<<drum[i]<<" ";
fout<<endl;
}
int main()
{
read();
//tipar();
next = 1;
while(poz)
{
bfs();
fnext();
// tipar_drum();
clear2();
}
bfs();
sol+=drum[n];
fout<<sol;//<<"*"<<endl;
// tipar_drum();
}