Cod sursa(job #2671708)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 12 noiembrie 2020 16:41:46
Problema PScNv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
// By Stefan Radu

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)(x).size()

typedef pair < int, int > pii;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

class Reader {
public:

  Reader(const char *name) {
    index = 0;
    f = fopen(name, "r");
    buff = (char*) malloc(LIMIT * sizeof(*buff));
    fread(buff, sizeof(char), LIMIT, f);
  }

  ~Reader() {
    free(buff);
    fclose(f);
  }

  Reader& operator >>(int &number) {
    number = 0;
    char c = getChar();
    while (not isdigit(c)) {
      c = getChar();
    }

    while (isdigit(c)) {
      number = number * 10 + (int) c - '0';
      c = getChar();
    }

    return *this;
  }

private:

  FILE *f;
  char *buff;
  int index;

  static const int LIMIT = 4096;

  char getChar() {
    if (index == LIMIT) {
      index = 0;
      fread(buff, sizeof(char), LIMIT, f);
    }

    return buff[index ++];
  }
};

Reader fin("pscnv.in");
ofstream fout("pscnv.out");

struct Edge {
  int nei, weight;
};

vector < bool > used;
vector < vector < Edge > > gr;

bool getMost(int node, int y, int &most) {

  if (node == y) return true;

  used[node] = true;
  for (auto edge : gr[node]) {
    if (used[edge.nei]) continue;

    most = max(most, edge.weight);
    if (getMost(edge.nei, y, most)) return true;
  }

  return false;
}


int main() {

#ifdef STEF
  freopen("input", "r", stdin);
  freopen("output", "w", stdout);
#endif

  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);

  int n, m, x, y;
  fin >> n >> m >> x >> y;

  gr.resize(n + 1);
  used.resize(n + 1);
  for (int i = 1; i <= m; ++ i) {
    int a, b, c;
    fin >> a >> b >> c;
    gr[a].push_back({b, c});
  }

  for (int i = 1; i <= n; ++ i) {
    sort(gr[i].begin(), gr[i].end(), [](Edge a, Edge b) -> bool {
        return a.weight < b.weight;
    });
  }

  int most = -1;
  getMost(x, y, most);
  fout << most << '\n';
}