Cod sursa(job #2611696)

Utilizator Data 7 mai 2020 14:15:24 Traseu 100 cpp-64 done Arhiva de probleme 3.96 kb
``````#include <bits/stdc++.h>

using namespace std;

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

const int INF = 1e9;
const int DIM = 62;

int cost[DIM][DIM];
int in[DIM];
int out[DIM];

struct Edge
{
int x;
int y;
int cap;
int cost;
};

struct Network
{
vector <Edge> edges;

vector <int> dist;

int n, S, D;

Network(int n, int S, int D) : n(n), S(S), D(D), adj(n + 1), dist(n + 1, INF) {}

void add_edge(int x, int y, int c, int z)
{
edges.emplace_back(Edge{x, y, c, z});

edges.emplace_back(Edge{y, x, 0, -z});
}

void bellman_ford()
{
vector <bool> inQ(n + 1, false);
queue <int> q;

q.push(S);
inQ[S] = true;

dist[S] = 0;

while(!q.empty())
{
int nod = q.front();
q.pop();

inQ[nod] = false;

{
if(edges[i].cap && dist[edges[i].y] > dist[nod] + edges[i].cost)
{
dist[edges[i].y] = dist[nod] + edges[i].cost;

if(!inQ[edges[i].y])
{
inQ[edges[i].y] = true;
q.push(edges[i].y);
}
}
}
}
}

{
dad = vector <int> (n + 1, -1);
vector <int> cost(n + 1, INF);

priority_queue <pair <int, int> > pq;

cost[S] = 0;

pq.push({0, S});

while(!pq.empty())
{
int nod = pq.top().second;
int val = pq.top().first;

pq.pop();

if(val != -cost[nod])
{
continue;
}

{
if(edges[i].cap && cost[edges[i].y] > cost[nod] + dist[nod] - dist[edges[i].y] + edges[i].cost)
{
cost[edges[i].y] = cost[nod] + dist[nod] - dist[edges[i].y] + edges[i].cost;

pq.push({-cost[edges[i].y], edges[i].y});
}
}
}

for(int i = 1; i <= n; i++)
{
dist[i] += cost[i];
}

}

int get_cost()
{
bellman_ford();

int cost = 0;

{
int cat = INF;

cat = min(cat, edges[i].cap);

{
cost += cat * edges[i].cost;
edges[i].cap -= cat;
edges[i ^ 1].cap += cat;
}
}

return cost;
}

};

main()
{
int n, m;
fin >> n >> m;

int ans = 0;

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

cost[x][y] = c;
ans += c;

++out[x];
++in[y];
}

for(int k = 1; k <= n; ++k)
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(i != j)
if(cost[i][k] && cost[k][j])
if(cost[i][j] == 0 || cost[i][j] > cost[i][k] + cost[k][j])
cost[i][j] = cost[i][k] + cost[k][j];

Network retea(n + 2, n + 1, n + 2);

for(int i = 1; i <= n; ++i)
if(in[i] > out[i])
{
retea.add_edge(n + 1, i, in[i] - out[i], 0);

for(int j = 1; j <= n; ++j)
if(out[j] > in[j])