Pagini recente » Cod sursa (job #2808368) | Cod sursa (job #1671202) | Cod sursa (job #3209366) | Cod sursa (job #3219923) | Cod sursa (job #670251)
Cod sursa(job #670251)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define DEBUG 0
#define MAXN 2002
#define INF 0x7fffffff
vector<int> Graf[MAXN];
vector<int> Cost[MAXN];
int Dist[MAXN];
bool Vis[MAXN];
int N, M;
#if DEBUG == 1
ofstream debug("debug.txt", ios::app);
#endif
int getMinDist(int from, int to)
{
#if DEBUG==1
debug<<"Shortest way between "<<from<<" and "<<to<<endl;
#endif
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, from));
while (!q.empty())
{
int c = q.top().first, v = q.top().second;
q.pop();
#if DEBUG==1
debug<<"Picked node "<<v<<" of cost "<<c;
#endif
if (Vis[v]) {
#if DEBUG==1
debug<<"...dumped\n";
#endif
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]));
}
#if DEBUG==1
debug<<endl<<"Distances: ";
for (int i=1; i<=N; i++)
if (Dist[i] == INF) debug<<"x ";
else debug<<Dist[i]<<" ";
debug<<endl;
#endif
}
#if DEBUG==1
debug<<"Final result: "<<Dist[to]<<endl;
#endif
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");
#if DEBUG==1
debug<<"------------------------------"<<endl;
#endif
// 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;
// Cleanup
in.close();
out.close();
#if DEBUG==1
debug.close();
#endif
return 0;
}