Pagini recente » Cod sursa (job #2126651) | Cod sursa (job #2732629) | Cod sursa (job #546400) | Cod sursa (job #2800280) | Cod sursa (job #1368588)
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define INF 1000000
using namespace std;
struct oras
{
vector <int> nod, cost;
};
oras g[2001];
queue <int> Q;
int a[2001], q[2001], Cost[2001], nr=0;
bool sel[2001], ok[2001], used[2001];
void dfs (int x)
{
int i; sel[x]=true; q[++nr]=x;
for (i=0; i<g[x].nod.size(); i++)
{
if (!sel[g[x].nod[i]])
{
dfs(g[x].nod[i]);
}
}
}
void bellmanford(int x, int n)
{
int i, nod;
while (!Q.empty()) Q.pop();
memset(Cost,0,sizeof(Cost));
memset(used,0,sizeof(used));
Q.push(x); used[1]=true;
for (i=1; i<=n; i++) if (i!=x) Cost[i]=INF;
while (!Q.empty())
{
nod=Q.front(); Q.pop();
used[nod]=false;
for (i=0; i<g[nod].nod.size(); i++)
{
if (Cost[nod]+g[nod].cost[i]<Cost[g[nod].nod[i]])
{
Cost[g[nod].nod[i]]=Cost[nod]+g[nod].cost[i];
if (!used[g[nod].nod[i]])
{
used[g[nod].nod[i]]=true;
Q.push(g[nod].nod[i]);
}
}
}
}
}
int main()
{
int n, m, k, i, x, y, z, sum=0;
freopen("ubuntzei.in","r",stdin);
freopen("ubuntzei.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for (i=1; i<=k; i++) {scanf("%d",&a[i]); ok[a[i]]=true;}
for (i=1; i<=m; i++)
{
scanf("%d%d%d",&x,&y,&z);
g[x].nod.push_back(y);
g[y].nod.push_back(x);
g[x].cost.push_back(z);
g[y].cost.push_back(z);
}
dfs(1); x=1;
for (i=2; i<=n; i++)
{
if (ok[q[i]]==true)
{
bellmanford(q[x],n);
sum+=Cost[q[i]];
x=i;
}
}
bellmanford(q[x],n);
if (ok[n]==false) sum+=Cost[n];
printf("%d",sum);
return 0;
}