Cod sursa(job #2263115)

Utilizator moltComan Calin molt Data 18 octombrie 2018 10:40:59
Problema Sate Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

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

struct sate {
    int y,dist;
};
bool viz[30005];
vector <sate> v[30005];
int rez;
int n,x,y,d,m,ns,nf;
void DFS(int ns) {
    viz[ns] = true;
    if (ns == nf)
        return;
    for (int i = 0; i < v[ns].size(); ++i) {
        if (viz[v[ns][i].y] == false) {
            rez += v[ns][i].dist;
            viz[v[ns][i].y] = true;
            DFS(v[ns][i].y);
        }
    }

}

int main() {

    in>>n>>m>>ns>>nf;
    for (int i = 1; i <= m; ++i) {
        in>>x>>y>>d;
        sate aux;
        aux.y = y;
        aux.dist = d;
        v[x].push_back(aux);
        sate auxinv;
        auxinv.y = x;
        auxinv.dist = -d;
        v[y].push_back(auxinv);
    }
    //for (int i = 1;i <= n;++i)
    //   for (int j = 0;j < v[i].size();++j)
    //     cout<<i<<" "<<v[i][j].y<<" "<<v[i][j].dist<<"\n";
    DFS(ns);
    out<<rez;
    return 0;
}