kampanja

#include <iostream>
#include <algorithm>
#include <cstring>

#define MAXN 105
#define MYINF 1000000
#define S 0
#define T 1

using namespace std;

int dist[MAXN][MAXN];
int ans[MAXN][MAXN];
bool solved[MAXN][MAXN];

int main (){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        dist[x][y] = 1;
    }

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(i != j and dist[i][j] == 0) dist[i][j] = MYINF;

    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    memset(ans, MYINF, sizeof(ans));
    ans[S][S] = 1; // let ans[i][j] be minimal nodes that have to pass when travel from i => 1 => j

    while(not solved[T][T]){
        int i = -1;
        int j = -1;
        int minvalue = MYINF;

        for(int x = 0; x < n; x++){
            for(int y = 0; y < n; y++){
                if((not solved[x][y]) and (ans[x][y] < minvalue)){
                    i = x;
                    j = y;
                    minvalue = ans[x][y];
                }
            }
        }

        solved[i][j] = true;

        for(int x = 0; x < n; x++){
            for(int y = 0; y < n; y++){
                if(not solved[x][y]){
                    int minnode = dist[x][i] + ans[i][j] + dist[j][y]; // case 1: x => (i => j) => y

                    if(x == y) minnode--; // case 2: x => (i => j) => x
                    else if(y != i and j != x) // case 3: x => y => i => (i => j) => x
                        minnode = min(minnode, dist[x][y] + dist[y][i] + ans[i][j] + dist[j][x] - 1);

                    ans[x][y] = min(ans[x][y], minnode);
                }
            }
        }
    }
    cout << ans[T][T] << endl;
    return 0;
}