Pagini recente » Cod sursa (job #2099972) | Cod sursa (job #652493) | Cod sursa (job #71465) | Cod sursa (job #708398) | Cod sursa (job #1249403)
/// Craciun Catalin
/// Ubuntzei
/// OJI 2011
#include <iostream>
#include <fstream>
#include <vector>
const int NMax = 2005;
const int inf = 1<<30;
struct graf {
int nod;
int cost;
graf *next;
};
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int n,m,k;
graf *a[NMax];
int pathLen = 0;
int toVisit[NMax];
int calculated[NMax];
int d[NMax], visited[NMax];
void add(int where, int what, int cost) {
graf *q = new graf;
q->nod = what;
q->cost = cost;
q->next = a[where];
a[where] = q;
}
void read() {
f>>n>>m;
f>>k;
for (int i=1;i<=k;i++) {
int x; f>>x;
toVisit[x] = 1;
}
toVisit[n] = 1;
for (int i=1;i<=m;i++) {
int x,y,z;
f>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
f.close();
}
void dijkstra(int startNode) {
d[startNode] = 0;
for (int i=1;i<=n;i++) {
visited[i] = 0;
if (i!=startNode)
d[i] = inf;
}
int min;
int pmin = 0;
for (int i=1;i<=n;i++) {
min = inf;
for (int j=1;j<=n;j++) {
if (!visited[j] && min > d[j]) {
min = d[j];
pmin = j;
}
}
visited[pmin] = 1;
graf *q = a[pmin];
while (q) {
if (d[q->nod] > d[pmin] + q->cost)
d[q->nod] = d[pmin] + q->cost;
q=q->next;
}
}
int minimum = inf, pminimum;
for (int i=1;i<=n;i++) {
if (i != startNode && toVisit[i] && minimum > d[i]) {
minimum=d[i]; pminimum = i;
}
}
toVisit[pminimum] = 0;
pathLen = pathLen + minimum;
if (pminimum != n)
dijkstra(pminimum);
}
int main() {
read();
dijkstra(1);
g<<pathLen<<'\n';
return 0;
}