Cod sursa(job #3374688)

Utilizator iooliahIulia Toader iooliah Data 9 noiembrie 2026 09:21:25
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

ifstream fin("sate.in");
ofstream fout("sate.out");

int n, m, x, y;
vector<vector<pair<int,int>>> adj;          //retin fiecare vecin si distanta pana la el
vector<int> viz,dist;                       //viz pt satele vizitate, dist pt distanta de la x la fiecare sat

void DFS(int nod){
    viz[nod]=1;
    for(auto i : adj[nod]){
        if(!viz[i.first]){
            dist[i.first] = dist[nod] + i.second;        //calculez distanta fata de x pentru fiecare vecin
            DFS(i.first);
        }
    }
}



int main()
{

    fin>>n>>m>>x>>y;
    adj.resize(n+5);
    viz.resize(n+5);
    dist.resize(n+5,0);

    for(int k=1; k<=m; k++){
        int i, j, d;
        fin>>i>>j>>d;
        adj[i].push_back({j,d});        //dist pozitiva de la i la j
        adj[j].push_back({i,-d});       //dist negativa de la j la i
    }

    DFS(x);

    fout<<dist[y];


    return 0;
}