Графы

#include <iostream>
#include <fstream>
#include <iomanip>
 
using namespace std;
 
#define SIZE 100
 
 
int a[SIZE][SIZE]; // матрица смежности
const int MAX_INT = 100000; // аналог бесконечности
int d[SIZE]; // d[i] - кратчайшее расстояние(сумма весов)из заданной вершины в i-тую
int used[SIZE]; // used[i] = 1 - i-тый узел посещен иначе used[i] = 0
int prev[SIZE]; // prev[i] - номер узла, из которого мы попадаем в узел i 
int inv_path[SIZE][SIZE]; // путь
int N, M; // количество узлов , кол-во ребер
int start, end; // начальный и конечный пункт
int path_len[SIZE]; // path_len[i] - длина массива inv_path для i-го пути
 
int find_the_shortest_way(int V1, int V2, int m); // (V1, V2) - ребро, которое мы удаляем из графа, 
// m - номер мин. пути, полученного при этом
 
int main()
{
    int min_record; // второе минимальное расстояние между двумя вершинами
    int i, j; 
    int x, y, k; // xy - ребро, k - вес
 
    char *s = "input.txt"; // имя файла
 
    ifstream in(s);
 
    if(!s) cout << "Can't open file " << s << endl;
 
    in >> N >> M;
 
    for(i = 0; i < N; i++)
        for(j = 0; j < N; j++)
            a[i][j] = 0; 
 
    for(i = 0; i < M; i++)
    {
        in >> x >> y >> k;
        a[x][y] = k; // граф ориентированный
        //a[y][x] = k;  // если граф неориентированный, то убрать метку
    }
 
    // Вывод матрицы смежности для графа
    for(i=0; i< N; i++)
    {
        for(j=0; j< N ; j++)
        {
            cout << setw(8) << a[i][j];
        }
        cout << endl;
    }
 
    cout << "Enter start point : "; cin >> start; // город А
    cout << "Enter end point : "; cin >> end; // город В
 
    int path = find_the_shortest_way(0,0,0); // Первый минимальный путь(основной путь)
 
    if(path == MAX_INT) cout << "There's no way from point " << start << " to point " << end << "." << endl;
    else
    {
       cout << "The first shortest way from "
            << start << " to " << end << ":";
       // Выводим путь
       for(int i=path_len[0]-1; i>=0; i--) {cout << " " << inv_path[0][i];}
       // Выводим его длину
       cout << " Path length is " << path << endl;
    }
 
    int n = 1; // счетчик для индексов пути
 
    min_record = MAX_INT;
    int d;
    int min_index; // номер второго минимального пути среди всех неосновных
 
    for(j = path_len[0] - 1; j>0; j--)
    {
        d = find_the_shortest_way(inv_path[0][j], inv_path[0][j-1], n);
        if(d < min_record)
        {
            min_record = d;
            min_index = n;
        }
        n++;
    }
    if(min_record == MAX_INT) cout << "There's no way from point " << start << " to point " << end << "." << endl;
    else
    {
       cout << "The second shortest way from "
            << start << " to " << end << ":";
       // Выводим путь
       for(int i=path_len[min_index]-1; i>=0; i--) {cout << " " << inv_path[min_index][i];}
       // Выводим его длину
       cout << " Path length is " << min_record << endl;
    }
    return 0;
}
 
int find_the_shortest_way(int V1, int V2, int m)
{
    int i, j, w, min_v;
 
 
    for(j=0;j<N;j++)
    {
        used[j] = 0;
        d[j] = MAX_INT;
    }
 
    prev[start] = -1;
    d[start] = 0; //  кратчайший путь из start в start = 0;
    used[start] = 1; // кратчайший путь для начальной вершины найден
    w = start; // текущая вершина
 
    // Алгоритм Дейкстры 
 
    while(1)
    {
 
        for(j=0; j<N; j++)
        {
            if(a[w][j] == 0 || (w == V1 && j == V2)) continue; // вершины w и j несмежные
            if(used[j] == 0 && d[j] > d[w]+a[w][j])
            {
                d[j] = d[w] + a[w][j];
                prev[j] = w;
            }
        }
        min_v = MAX_INT;
        w = -1 ;
 
        for(j=0; j<N; j++)
        {
            if(used[j] == 0 && d[j] < min_v)
            {
                min_v = d[j];
                w = j;
            }
        }
        if(w == -1) 
        {
            return MAX_INT; 
        }
        if(w==end)
        {
            j = end; int k = 0;
            while(j!=-1)
            {
                inv_path[m][k] = j;
                j = prev[j];
                k++;
            }
            path_len[m] = k;
            return d[end];
        }
        used[w] = 1;
    }
}

in >>