# Cod sursa(job #2731171)

Utilizator Data 27 martie 2021 14:06:34 Traseu 100 cpp-64 done Arhiva de probleme 2.92 kb
``````#include <iostream>
#include <fstream>
#include <algorithm>
#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, maxSize, source, sink;
int minCost, maxFlux;
vector<int> g[N], realDist, newRealDist, positiveDist;
vector<bool> vizitat;

void BellmanFord()
{
realDist.assign(maxSize, INF);

realDist[source] = 0;

{

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

{
}
}
}
}
}

void Dijkstra()
{
positiveDist.assign(maxSize, INF);
newRealDist.assign(maxSize, INF);
vizitat.assign(maxSize, false);

positiveDist[source] = newRealDist[source] = 0;

priority_queue<pair<int, int>> heap;
heap.push({ 0, source });

while (!heap.empty())
{
int x = heap.top().second;
heap.pop();

if (vizitat[x])
continue;

vizitat[x] = true;

for (int y : g[x])
{
int positiveCostXY = realDist[x] + cost[x][y] - realDist[y];

if (!vizitat[y] && flow[x][y] != cap[x][y] && positiveDist[x] + positiveCostXY < positiveDist[y])
{
positiveDist[y] = positiveDist[x] + positiveCostXY;
heap.push({ -positiveDist[y], y });
newRealDist[y] = newRealDist[x] + cost[x][y];
t[y] = x;
}
}
}

realDist = newRealDist;
}

void MaxFluxMinCost()
{
BellmanFord();

while (true)
{
Dijkstra();

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

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

minCost += realDist[sink] * minFlux;
maxFlux += minFlux;

for (int node = sink; node != source; node = t[node])
{
flow[t[node]][node] += minFlux;
flow[node][t[node]] -= minFlux;
}
}
}

void AddEdge(int x, int y, int capacitate, int pret)
{
g[x].push_back(y);
g[y].push_back(x);
cap[x][y] = capacitate;
cost[x][y] = pret;
cost[y][x] = -pret;
}

int main()
{
fin >> n >> m;
source = 0;
sink = n + 1;
maxSize = sink + 1;

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++)
{