Pagini recente » Cod sursa (job #161823) | Cod sursa (job #534692) | Cod sursa (job #240418) | Cod sursa (job #2340672) | Cod sursa (job #670244)
Cod sursa(job #670244)
#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;
}