Cod sursa(job #3185531)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 19 decembrie 2023 13:17:42
Problema Sate Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>

#define DIM 30000

//#define int long long

using namespace std;

//ifstream f("in.in");
//ofstream g("out.out");

ifstream f("sate.in");
ofstream g("sate.out");

int n,m;
int x,y;
int a,b,c;
int dp[DIM+5];
vector <pair<int,int>> L[DIM+5];
deque <int> q;

void pathfind(int start){

    q.push_back(start);
    dp[start] = 0;

    while(!q.empty()){

        int x = q.front();
        q.pop_front();

        for(int i = 0;i < L[x].size();i++){
            int y = L[x][i].first;
            int cost = L[x][i].second;

            if(dp[y] == -1){
                dp[y] = dp[x] + cost;
                q.push_back(y);
            }
        }
    }
}

signed main(){

    f>>n>>m>>x>>y;
    for(int i=1;i<=m;i++){
        f>>a>>b>>c;

        L[a].push_back({b,c});
        L[b].push_back({a,-c});
    }

    for(int i=1;i<=n;i++){
        dp[i] = -1;
    }

    pathfind(x);

    g<<dp[y];


    return 0;
}