Cod sursa(job #3255350)

Utilizator aeru1Ianos Alex-Marian aeru1 Data 10 noiembrie 2024 13:53:36
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
    #include <bits/stdc++.h>

    using namespace std;

    #define ll long long
    #define TITLE "sate"

    ifstream f (TITLE".in");
    ofstream g (TITLE".out");

    int n,m,StartNode,EndNode;

    void bfs(int StartNode,vector<vector<pair<int,int>>> &Graph, vector<int> &Visited)
    {
        queue<int>Q;
        Visited[StartNode]=1;
        for(Q.emplace(StartNode); !Q.empty(); Q.pop())
        {
            int CurrentNode=Q.front();
            for(auto it: Graph[CurrentNode])
            {
                if(Visited[it.first]==0)
                {
                    Visited[it.first]=Visited[CurrentNode]+it.second;
                    Q.emplace(it.first);
                }
            }
        }
    }

    int main()
    {
        f>>n>>m>>StartNode>>EndNode;
        vector<vector<pair<int,int>>> Graph(n+1);
        while(m--)
        {
            int a,b,c;
            f>>a>>b>>c;
            if(a>b)
                swap(a,b);
            Graph[a].push_back({b,c});
            Graph[b].push_back({a,-c});
        }
        vector<int>Answer(n+1,0);
        bfs(StartNode,Graph,Answer);
        g<<Answer[EndNode]-1;
        return 0;
    }