Cod sursă (job #313825)

#include <fstream>
#include <queue>
#include <vector>

using namespace std;

struct Node
{
  int dragon;
  vector<pair<int, int>> edges;
};

typedef vector<Node> Graph;

const int kMaxDragon = 50000;
const int kInf = 1 << 30;

int FindBestDragon(const Graph &g, int node, int dragon)
{
  int best = g[node].dragon;
  queue<int> q;
  vector<bool> visited(g.size(), false);

  q.push(node);
  visited[node] = true;

  while (!q.empty()) {
    node = q.front();
    q.pop();

    best = max(best, g[node].dragon);
    for (const auto &p : g[node].edges) {
      if (!visited[p.first] && p.second <= dragon) {
        q.push(p.first);
        visited[p.first] = true;
      }
    }
  }
  return best;
}

int FindMinDist(const Graph &g, int start, int stop)
{
  vector<vector<int>> min_dist(g.size(), vector<int>(kMaxDragon + 1, kInf));
  queue<pair<int, int>> q;

  min_dist[start][g[start].dragon] = 0;
  q.push({start, g[start].dragon});

  while (!q.empty()) {
    auto node = q.front().first;
    auto dragon = q.front().second;
    q.pop();

    for (const auto &p : g[node].edges) {
      auto next = p.first;
      auto cost = p.second;
      if (dragon < cost) {
        continue;
      }

      auto dist = min_dist[node][dragon] + cost;
      auto next_dragon = max(dragon, g[next].dragon);
      if (dist < min_dist[next][next_dragon]) {
        min_dist[next][next_dragon] = dist;
        q.push({next, next_dragon});
      }
    }
  }

  auto res = kInf;
  for (const auto &dist : min_dist[stop]) {
    res = min(res, dist);
  }
  return res;
}

int main()
{
  ifstream fin("dragoni2.in");
  ofstream fout("dragoni2.out");

  int type;
  fin >> type;

  int nodes, edges;
  fin >> nodes >> edges;

  Graph graph(nodes);
  for (auto &node : graph) {
    fin >> node.dragon;
  }

  for (int i = 0; i < edges; ++i) {
    int x, y, d;
    fin >> x >> y >> d;
    graph[x - 1].edges.push_back({y - 1, d});
    graph[y - 1].edges.push_back({x - 1, d});
  }

  if (type == 1) {
    auto dragon = FindBestDragon(graph, 0, graph[0].dragon);
    fout << dragon << "\n";
    return 0;
  }

  auto dist = FindMinDist(graph, 0, nodes - 1);
  fout << dist << "\n";

  return 0;
}