Cod sursa(job #1398532)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 24 martie 2015 11:49:18
Problema Sate Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

#define inFile "sate.in"
#define outFile "sate.out"
#define MAX_N 30001
#define DEFAULT 1<<30

struct edge {
    int y;
    int cost;
} e;

int s[MAX_N];
vector < edge > v[MAX_N];
queue < int > q;

int main() {
    ifstream in(inFile);
    ofstream out(outFile);
    
    int n, m, x, y, i, n1, n2, dist;
    
    in >> n >> m >> x >> y;
    for(i = 1; i <= m; i++) {
        in >> n1 >> n2 >> dist;
        v[n1].push_back({n2, dist});
        v[n2].push_back({n1, -dist});
    }
    
    memset(s, 0, sizeof(s));
    s[x] = 1;
    q.push(x);
    
    while(!q.empty()) {
        n1 = q.front();
        q.pop();
        
        for(i = 0; i < v[n1].size(); i++) {
            n2 = v[n1][i].y;
            
            if(!s[n2]) {
                s[n2] = s[n1] + v[n1][i].cost;
                q.push(n2);
            }
        }
    }
    
    out << abs(s[y])-1 << '\n';
    
    return 0; 
}