Cod sursa(job #3207745)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 26 februarie 2024 20:49:17
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream cin("sate.in");
ofstream cout("sate.out");
int n , m  , x, y,where[30001];
vector<pair<int,int>> adj[30001];
int main()
{
    cin >> n >> m >> x >> y;
    for ( int i = 1; i <= m ; i ++  )
    {
        int a, b, c;
        cin >> a>> b>> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    vector<bool>viz(n+1,0);

    for ( int i = 1; i <= n ; i ++ )
    {
        if ( viz [i] == 0 )
        {
            queue<int> q;
            where[i] = where[i-1] + 1;
            viz[i] = true;
            q.push(i);
            while(!q.empty() )
            {
                int nod = q.front();

                for ( auto u :adj[nod] )
                {
                    if ( viz[u.first] )
                        continue;

                    if ( nod > u.first )
                    {
                        where[u.first] = where[nod] - u .second;
                    }
                    else
                        where[u.first] = where[nod] + u.second;
                        viz[u.first] = true ;
                    q.push(u.first);
                }
                q.pop();
            }
        }
    }

    cout << where[y] - where[x] << '\n';
    return 0;
}