Cod sursa(job #1249393)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 26 octombrie 2014 22:29:53
Problema Ubuntzei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
/// 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;
}