Cod sursa(job #2243530)

Utilizator Dragne.Andrei11Dragne Andrei Dragne.Andrei11 Data 20 septembrie 2018 19:59:50
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const short nmax=30005;

vector <pair<int, int> > graph[nmax];
int dist[nmax];
bool visited[nmax];

int n, m, x, y;

void bfs(int start_node)
{
    dist[start_node]=0;
    queue<int> bfsqueue;
    bfsqueue.push(start_node);
    visited[start_node]=true;
    while(!bfsqueue.empty())
    {
        int current_node=bfsqueue.front();
        bfsqueue.pop();
        for(int i=0;i<graph[current_node].size();i++)
        {
            if(!visited[graph[current_node][i].first])
            {
                visited[graph[current_node][i].first]=true;
                bfsqueue.push(graph[current_node][i].first);
                dist[graph[current_node][i].first]+=dist[current_node]+graph[current_node][i].second;
            }
        }
    }
}

int main()
{
    freopen("sate.in", "r", stdin);
    freopen("sate.out", "w", stdout);

    scanf("%d%d%d%d", &n, &m, &x, &y);
    for(int i=1;i<=m;i++)
    {
        int k, l, d;
        scanf("%d%d%d", &k, &l, &d);
        graph[k].push_back(make_pair(l, d));
        graph[l].push_back(make_pair(k, d*(-1)));
    }
    bfs(x);
    if(dist[y]==0)
        printf("-1");
    else
        printf("%d\n", dist[y]);

    return 0;
}