# Cod sursa(job #2730686)

Utilizator Data 26 martie 2021 18:04:09 Traseu 100 cpp-64 done Arhiva de probleme 2.45 kb
``````#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int N = 65;
const int INF = 1e9;

int n, m, fmax, costMin, gn;
vector<int> dist;
vector<int> g[N];
vector<bool> vis;

{
dist.assign(gn, INF);

dist[startNode] = 0;
t[startNode] = 0;

{

for (int y : g[x])
{
if (dist[x] + cost[x][y] < dist[y] && flow[x][y] != cap[x][y])
{
t[y] = x;
dist[y] = dist[x] + cost[x][y];
{
}
}
}
}
}

void maxFlowMinCost(int source, int sink)
{
do
{

if(dist[sink] == INF)
break;

int fmin = 1 << 30;
for(int node = sink; node != source; node = t[node])
fmin = min(fmin, cap[t[node]][node] - flow[t[node]][node]);

fmax += fmin;
costMin += dist[sink] * fmin;
for(int node = sink; node != source; node = t[node])
{
flow[t[node]][node] += fmin;
flow[node][t[node]] -= fmin;
}
} while(dist[sink] != INF);
}

void addEdge(int x, int y, int c, int z)
{
g[x].push_back(y);
g[y].push_back(x);
cap[x][y] = c;
cap[y][x] = 0;
cost[x][y] = z;
cost[y][x] = -z;
}

int main()
{
fin >> n >> m;
gn = n + 2;

int ans = 0;
for (int i = 1; i <= m; i++)
{
int x, y, c;
fin >> x >> y >> c;
ans += c;

}

for (int i = 1; i <= n; i++)
{