Pagini recente » Cod sursa (job #978327) | Cod sursa (job #2139765) | Cod sursa (job #3193427) | Cod sursa (job #2464706) | Cod sursa (job #1249393)
/// 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];
vector<int> toVisit;
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.push_back(x);
}
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();
}
int dijkstra(int startNode, int finishNode) {
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;
}
}
return d[finishNode];
}
int main() {
toVisit.push_back(1);
read();
toVisit.push_back(n);
int pathLen = 0;
for (unsigned int i=0;i<toVisit.size()-1;i++)
pathLen += dijkstra(toVisit[i], toVisit[i+1]);
g<<pathLen<<'\n';
return 0;
}