Pagini recente » Diferente pentru problema/numere9 intre reviziile 8 si 7 | Monitorul de evaluare | Monitorul de evaluare | Borderou de evaluare (job #1835466) | Cod sursa (job #3357705)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
using PI = pair<int, int>;
using VI = vector<int>;
using VPI = vector<PI>;
using VVI = vector<VI>;
using VVPI = vector<VPI>;
using VB = vector<bool>;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
struct Cell {
int x, w;
Cell(int x = 0, int w = 0) : x {x}, w {w}
{}
bool operator < (Cell const& other) const noexcept
{
return w > other.w;
}
};
const int INF = 0x3f3f3f3f;
int n, m, k;
VI nodes, d;
VB v;
VVPI adj;
void ReadInput();
void Dijsktra(int x, VI& d);
int main()
{
ReadInput();
int currNode(1), ans(0);
while (true)
{
if (currNode == n)
break;
Dijsktra(currNode, d);
int minDist(INF), nextNode;
for (int i = 1; i <= k; ++i)
{
if (v[i])
continue;
if (d[i] < minDist)
{
minDist = d[i];
nextNode = nodes[i];
}
}
ans += d[nextNode];
currNode = nextNode;
}
fout << ans;
return 0;
}
void Dijsktra(int x, VI& d)
{
priority_queue<Cell> Q;
d = VI(n + 1, INF);
Q.emplace(x, 0);
d[x] = 0;
int y, w;
while (!Q.empty())
{
auto [x, dist] = Q.top();
Q.pop();
if (dist > d[x])
continue;
for (auto node : adj[x])
{
y = node.first;
w = node.second;
if (d[y] > d[x] + w)
{
d[y] = d[x] + w;
Q.emplace(y, d[y]);
}
}
}
}
void ReadInput()
{
fin >> n >> m >> k;
k++;
v = VB(k + 1);
nodes = VI(k + 1);
adj = VVPI(n + 1);
for (int i = 1; i <= k; ++i)
fin >> nodes[i];
nodes[k] = n;
int x, y, w;
for (int i = 1; i <= m; ++i)
{
fin >> x >> y >> w;
adj[x].emplace_back(y, w);
adj[y].emplace_back(x, w);
}
}