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;
}