Cod sursa(job #1899272)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 2 martie 2017 17:04:59
Problema Sate Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0);
#define tie cin.tie(0);
#define mp make_pair
#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define inf 1000000000
#define zeros(x) ( (x ^ (x - 1)) & x )

using namespace std;

int n, m, x, y, z, in, sf;

vector < int > V[100100];
map < PII, int > M;
int cost[100100];

void dfs(int x)
{
    for (auto it : V[x])
    {
        if (!cost[it])
        {
            cost[it] = cost[x] + M[mp(x, it)];
            dfs(it);
        }
    }
}


int main(){
    IOS tie
    ifstream cin("sate.in");
    ofstream cout("sate.out");
    cin >> n >> m >> in >> sf;
    if (in > sf) swap(in, sf);
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        V[x].push_back(y);
        V[y].push_back(x);
        M[mp(x, y)] = z;
        M[mp(y, x)] = -z;
    }
    dfs(in);
	cout << cost[sf];
	cerr << "Fucking time elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}