Cod sursa(job #670244)

Utilizator chibicitiberiuChibici Tiberiu chibicitiberiu Data 28 ianuarie 2012 18:56:25
Problema Ubuntzei Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>
//#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define MAXN 2002
#define INF 0x7fffffff

vector<int> Graf[MAXN];
vector<int> Cost[MAXN];
int Dist[MAXN];
bool Vis[MAXN];
int N, M;

int getMinDist(int from, int to)
{
	priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > q;

	for (int i = 1; i<= N; i++) {
		Dist[i] = INF; Vis[i] = false;
	}
	Dist[from] = 0;

	q.push(make_pair(0, 1));

	while (!q.empty())
	{
		int c = q.top().first, v = q.top().second;
		q.pop();

		if (Vis[v]) continue;
		Vis[v] = true;

		for (int i=0; i<Graf[v].size(); i++)
			if (Dist[Graf[v][i]] >= c + Cost[v][i])
			{
				Dist[Graf[v][i]] = c + Cost[v][i];
				q.push(make_pair(Dist[Graf[v][i]], Graf[v][i]));
			}

	}

	return Dist[to];
}

int main()
{
	int K, x, y, c;
	int sum=0;
	queue<int> work;

	// Open files
	ifstream in("ubuntzei.in");
	ofstream out("ubuntzei.out");

	// Read N,M,K
	in>>N>>M>>K;

	// Read vertices that must be visited
	work.push(1);
	while (K-- > 0) {
		in>>x; work.push(x);
	}
	work.push(N);

	// Read edges
	for (int i=0; i<M; i++)
	{
		in>>x>>y>>c;
		Graf[x].push_back(y);
		Cost[x].push_back(c);
	}

	// Do work
	while (work.size() >= 1)
	{
		int from = work.front(); work.pop();
		sum += getMinDist(from, work.front());
	}

	out<<sum;
	//cout<<sum;

	// Cleanup
	in.close();
	out.close();
	return 0;
}