Cod sursă (job #313841)

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

using namespace std;

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

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

  Node() : min_dist(kInf), max_dragon(0) {}
};

typedef vector<Node> Graph;

struct State
{
  int node, dragon, dist;
};

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(Graph &g, int start, int stop)
{
  queue<State> q;
  q.push({start, g[start].dragon, 0});

  g[start].max_dragon = g[start].dragon;
  g[start].min_dist = 0;

  int res = kInf;
  while (!q.empty()) {
    auto node = q.front().node;
    auto dragon = q.front().dragon;
    auto dist = q.front().dist;
    q.pop();

    if (node == stop) {
      res = min(res, dist);
      continue;
    }

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

      auto new_dist = dist + p.second;
      auto new_dragon = max(dragon, g[next].dragon);

      if (new_dist < g[next].min_dist || new_dragon > g[next].max_dragon) {
        g[next].min_dist = min(g[next].min_dist, new_dist);
        g[next].max_dragon = max(g[next].max_dragon, new_dragon);
        q.push({next, new_dragon, new_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;
}