Pagini recente » Cod sursa (job #384570) | Cod sursa (job #1733808) | Monitorul de evaluare | Cod sursa (job #597340) | Cod sursa (job #901846)
Cod sursa(job #901846)
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#define v first
#define c second
using namespace std;
ifstream in("ubuntzei.in");
ofstream out("ubuntzei.out");
const int maxn = 2013;
const int inf = 0x7fffffff;
int N, M, K, x, y, c;
typedef pair<int, int> vecin;
vector<vecin> vecini[maxn]; // Lista vecinilor fiecarui nod
int dist[maxn]; // Distantele
vector<int> prieteni; // Losta prietenilor
struct cmp {
bool operator() (const int& a, const int& b) {
return dist[a] > dist[b];
}
};
bool comp(const int& a, const int& b) { return dist[a] < dist[b]; }
priority_queue<int, vector<int>, cmp> qu; // Coada de prioritati
void dijkstra(int beg, int end)
{
fill(dist+1, dist+N+1, inf);
dist[beg] = 0;
qu.push(beg);
int here = 0;
while (!qu.empty() && here != end)
{
here = qu.top(); qu.pop();
for (int i = 0; i < vecini[here].size(); i++)
{
vecin vec = vecini[here][i];
if (dist[here] + vec.c < dist[vec.v])
{
dist[vec.v] = dist[here] + vec.c;
qu.push(vec.v);
}
}
}
}
int main()
{
in >> N >> M >> K;
for (int i = 0; i < K; i++) { in >> x; prieteni.push_back(x); }
for (int i = 0; i < M; i++)
{
in >> x >> y >> c;
vecini[x].push_back(make_pair(y, c));
vecini[y].push_back(make_pair(x, c));
}
dijkstra(1, N);
sort(prieteni.begin(), prieteni.end(), comp);
int i; int mini = dist[prieteni[0]];
for (i = 0; i < prieteni.size()-1; i++)
{
dijkstra(prieteni[i], prieteni[i+1]);
mini += dist[prieteni[i+1]];
}
dijkstra(prieteni[i], N);
mini += dist[N];
out << mini;
return 0;
}