Cod sursa(job #2447130)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 12 august 2019 11:37:19
Problema Sate Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("sate.in");
ofstream fout ("sate.out");

const int MAXN = 3000001;
int dp[MAXN],n,m,x,y;

struct muc {

    int x,y,d;
    bool operator < ( const auto & next) const  {
        return (y < next.y);
    };
};
muc a[MAXN];
int main() {

    fin >> n >> m >>  x >> y;
    for ( int i = 1; i <= m; ++i)
        fin >> a[i].x >> a[i].y >> a[i].d;
  //  sort(a + 1, a+ 1 + m);
    dp[x] = 1;
    while ( !dp[y]) {
        for ( int i = 1; i <= m; ++i)
            if (!dp[a[i].y] and dp[a[i].x])
                dp[a[i].y] = dp[a[i].x]+ a[i].d;
            else
            if (!dp[a[i].x] and dp[a[i].y]) {
                dp[a[i].x] = dp[a[i].y] - a[i].d;
            }
    }
    fout << dp[y]-1;
}