Hey Codeforces, I have question in this problem my code run as follow:
run Dijkstra to get the shortest path
run Dijkstra again to see if any edge get to the destination with cost > shortest_path then cancel this edge
run max flow with vertex split
why this approach is wrong ?! thanks in advance.
this is my code :
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000 * 1000 * 1000;
int n,m;
int g[105][105], cost;
int dijkstra(int source){
vector<int > dist(105, INF);
dist[source] = 0;
set<pair<int, int > > q;
q.insert(make_pair(0, source));
while(!q.empty()){
int current = q.begin()->second;
int distance = q.begin()->first;
q.erase(q.begin());
if(current == n-1) return distance;
for(size_t i = 0; i < n; ++i)
{
if(g[current][i] + distance < dist[i]){
if(q.count(make_pair(dist[i], i))) q.erase(make_pair(dist[i], i));
dist[i] = g[current][i] + distance;
q.insert(make_pair(dist[i], i));
}
}
}
return dist[n-1];
}
void dijkstrA(int source){
vector<int > dist(105, INF);
dist[source] = 0;
set<pair<int, int > > q;
q.insert(make_pair(0, source));
while(!q.empty()){
int current = q.begin()->second;
int distance = q.begin()->first;
q.erase(q.begin());
for(size_t i = 0; i < n; ++i)
{
//cout << distance << " " << g[current][i] << " " << current << " " << i << endl,
if(g[current][i] + distance > cost && i == n-1) g[current][i] = INF;
if(g[current][i] + distance < dist[i]){
if(q.count(make_pair(dist[i], i))) q.erase(make_pair(dist[i], i));
dist[i] = g[current][i] + distance;
q.insert(make_pair(dist[i], i));
}
}
}
}
int c[205][205];
int flow[205][205];
int bottleneck[205];
int pre[205];
void build()
{
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(g[i][j] < INF) c[i*2+1][j * 2] = INF;//, cout << i << " " << j << endl;
}
}
}
int maxflow(){
int ans = 0;
for(int i = 0; i <= 100; ++i) c[i*2][i*2+1] = 1;
c[0][1] = INF;
c[2*(n-1)][2*(n-1)+1] = INF;
int S = 0, T = 2*(n-1)+1;
while(1){
memset(bottleneck, 0, sizeof bottleneck);
bottleneck[0] = INF;
queue<int > q; q.push(0);
while(!q.empty()&&!bottleneck[T]){
int cur = q.front(); q.pop();
for(int i = S; i <= T; i++){
if(!bottleneck[i]&&c[cur][i] > flow[cur][i]){
q.push(i);
pre[i] = cur;
bottleneck[i] = min(bottleneck[cur], c[cur][i] - flow[cur][i]);
}
}
}
if(bottleneck[T] == 0) break;
for (int cur = T; cur != 0; cur = pre[cur]) {
flow[pre[cur]][cur] += bottleneck[T];
flow[cur][pre[cur]] -= bottleneck[T];
}
ans += bottleneck[T];
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
for(int i = 1,a,b,c; i <= m; ++i)
{
scanf("%d%d%d",&a,&b,&c);
g[a][b] = min(c,g[a][b]);
g[b][a] = min(c,g[b][a]);
}
cost = dijkstra(0);
dijkstrA(0);
build();
cost = maxflow();
if(cost == INF) cout << "IMPOSSIBLE" << endl;
else cout << cost << endl;
return 0;
}