Cod sursa(job #3371777)

Utilizator AlexPopescuPopescu Alexandru AlexPopescu Data 31 octombrie 2026 17:19:55
Problema Sate Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("sate.in");
ofstream fout("sate.out");
  void dfs(int node,vector<vector<pair<int,int>>>&graph,vector<bool>&visited,vector<int>&distances)
     {   
        stack<int>node_list;
       node_list.push(node);
       visited[node]=true;
       while(!node_list.empty()) 
       {int current_node=node_list.top();
        
        node_list.pop();
        for(auto& neighbour:graph[current_node])
            if(!visited[neighbour.first])
               {node_list.push(neighbour.first);
                  visited[neighbour.first]=true;
                if(neighbour.first>current_node)
                    distances[neighbour.first]=distances[current_node]+neighbour.second;
                else distances[neighbour.first]=distances[current_node]-neighbour.second; }  
       } 

     }
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,M,X,Y;
    fin>>N>>M>>X>>Y;
    assert(1<=N&&N<=3e5);
    assert(1<=M&&M<=1e6+24);
    vector<vector<pair<int,int>>>graph(N+1);
    vector<bool>visited(N+1,0);
    vector<int>distances(N+1,0);
    for(int i=1;i<=M;i++) 
       { int node1,node2,distance;
          fin>>node1>>node2>>distance;
         graph[node1].push_back({node2,distance});
         graph[node2].push_back({node1,distance});  
       }
    for(int i=1;i<=N;i++)
       {if(!visited[i])
             dfs(i,graph,visited,distances);        
          if(visited[Y])
             fout<<abs(distances[Y]-distances[X]);
              
            
          
        }
       
    return 0;
}