Cod sursa(job #1503942)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 17 octombrie 2015 09:38:16
Problema Sate Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <iostream>
#include <vector>
#include <string.h>
#include <fstream>
#include <queue>

using namespace std;

const int maxn = 30005;

int n, m, x, y, dist[maxn];
vector<pair<int, int> > g[maxn];

const int lim = (1 << 16);
char buff[lim];
int pos;

void getNr(int &numar) {
    numar = 0;
    while(!isdigit(buff[pos])) {
        if(++ pos == lim) {
            pos = 0;
            fread(buff, 1, lim, stdin);
        }
    }
    while(isdigit(buff[pos])) {
        numar = numar * 10 + buff[pos] - '0';
        if(++ pos == lim) {
            pos = 0;
            fread(buff, 1, lim, stdin);
        }
    }
}

int main()
{
    freopen("sate.in", "r", stdin);
    freopen("sate.out", "w", stdout);
    getNr(n);
    getNr(m);
    getNr(x);
    getNr(y);
    for(int i = 1 ; i <= m ; ++ i) {
        int x, y, z;
        getNr(x);
        getNr(y);
        getNr(z);
        g[x].push_back(make_pair(y, z));
        g[y].push_back(make_pair(x,-z));
    }
    memset(dist, -1, sizeof(dist));
    queue <int> q;
    q.push(x);
    dist[x] = 0;
    while(!q.empty()) {
        int node = q.front();
        q.pop();
        for(auto el : g[node]) {
            if(dist[el.first] == -1) {
                dist[el.first] = dist[node] + el.second;
                q.push(el.first);
            }
        }
    }
    printf("%d\n", dist[y]);
    return 0;
}