Cod sursa(job #3373063)

Utilizator Andygamer7Negoita Andrei Andygamer7 Data 6 noiembrie 2026 00:06:48
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <vector>

using namespace std;

struct Neighbor {
  int target, dist;
};

vector<vector<Neighbor>> graph;
vector<bool> seen;

int y, ans;
bool found = false;
void dist_to_y(int x, int dist_so_far = 0) {
  if (found)
    return;
  if (x == y) {
    ans = dist_so_far > 0 ? dist_so_far : -dist_so_far;
    found = true;
    return;
  }

  seen[x] = true;
  for (auto neighbor : graph[x]) {
    if (!seen[neighbor.target])
      dist_to_y(neighbor.target, dist_so_far + neighbor.dist);
  }
}

int main() {
  // facem DFS de la x la y. O sa punem distanta cu + daca e de la mic la mare
  // si cu - daca e de la mare la mic
  ifstream fin("sate.in");
  ofstream fout("sate.out");

  int n, m, x; // pe y il punem in afara

  fin >> n >> m >> x >> y;

  graph.resize(n + 1);
  seen.resize(n + 1);

  int a, b, d;
  for (int i = 0; i < m; i++) {
    fin >> a >> b >> d;
    int ascending;
    if (a < b)
      ascending = 1;
    else
      ascending = -1;

    graph[a].push_back(Neighbor{b, d * ascending});
    graph[b].push_back(Neighbor{a, -d * ascending});
  }

  dist_to_y(x);
  fout << ans;
}