Cod sursa(job #2541599)

Utilizator Giulian617Buzatu Giulian Giulian617 Data 8 februarie 2020 17:13:37
Problema Sate Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("sate.in");
ofstream g("sate.out");
int n,m,x,y,X,Y,D,sum[30005];
vector<pair<int,int> >v[30005];
bitset<30005>viz;
queue<int>q;
void bfs(int x)
{
    q.push(x);
    viz[x]=1;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(int i=0; i<v[x].size(); i++)
            if(viz[v[x][i].first]==0)
            {
                q.push(v[x][i].first);
                viz[v[x][i].first]=1;
                sum[v[x][i].first]=sum[x]+v[x][i].second;
                if(v[x][i].first==y)
                    return;
            }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    f>>n>>m>>x>>y;
    for(int i=1; i<=m; i++)
    {
        f>>X>>Y>>D;
        v[X].push_back({Y,D});
        v[Y].push_back({X,-D});
    }
    bfs(x);
    g<<sum[y];
    return 0;
}