daily pastebin goal
8%
SHARE
TWEET

Untitled

a guest Mar 26th, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "ReadWriter.h"
  2. //string, fstream, iostream, vector, Edge.h - included in ReadWriter.h
  3. #include <algorithm>
  4. #include <climits>
  5.  
  6.  
  7. using namespace std;
  8. // write all values
  9. void ReadWriter::writeValues(std::vector<std::vector<int>>& result)
  10. {
  11.     if (!fout.is_open())
  12.         throw std::ios_base::failure("file not open");
  13.  
  14.     string output;
  15.     int N = result.size();
  16.     for(int i = 0; i < N; i++)
  17.     {
  18.         for (int j = 0; j < N; j++)
  19.         {
  20.             if (i != j)
  21.             {
  22.                 if (result[i][j] == INT_MAX)
  23.                     result[i][j] = -1;
  24.                 output = to_string(i) + " " + to_string(j) + " " + to_string(result[i][j]) + "\n";
  25.                 fout << output;
  26.             }
  27.         }
  28.     }
  29. }
  30.  
  31. // Матричное возведение в квадрат с заменой умножения на выбор минимум
  32. void squareMatrix(vector<vector<int>> &A)
  33. {
  34.     int N = A.size();
  35.     for(int i = 0; i < N; i++)
  36.     {
  37.         for(int j = 0; j < N; j++)
  38.         {
  39.             if(i != j)
  40.             {
  41.                 for (int k = 0; k < N; k++)
  42.                 {
  43.                     // Если ребра существуют
  44.                     if (A[i][k] < INT_MAX && A[k][j] < INT_MAX)
  45.                         A[i][j] = min(A[i][k] + A[k][j], A[i][j]);
  46.                 }
  47.             }
  48.         }
  49.     }
  50. }
  51.  
  52. // Матричное умножение с заменой умножения на выбор минимума
  53. void multiplyMatrix(vector<vector<int>> &A, vector<vector<int>> &B)
  54. {
  55.     int N = A.size();
  56.     for(int i = 0; i < N; i++)
  57.     {
  58.         for(int j = 0; j < N; j++)
  59.         {
  60.             if(i != j)
  61.             {
  62.                 for (int k = 0; k < N; k++)
  63.                 {
  64.                     if (A[i][k] < INT_MAX && B[k][j] < INT_MAX)
  65.                         A[i][j] = min(A[i][k] + B[k][j], A[i][j]);
  66.                 }
  67.             }
  68.         }
  69.     }
  70. }
  71.  
  72. void solve(int N, int M, vector<Edge>& edges, vector<vector<int>>& matrix)
  73. {
  74.     // Создаем матрицу. Отсутствие ребра = INT_MAX
  75.     for(int i = 0; i < N; i++)
  76.         matrix[i] = vector<int>(N, INT_MAX);
  77.  
  78.     // Переписываем список ребер в матрицу смежности
  79.     for(int i = 0; i < M; i++)
  80.         matrix[edges[i].A][edges[i].B] = edges[i].W;
  81.  
  82.     // Матрица весов
  83.     vector<vector<int>> W = vector<vector<int>>(matrix);
  84.  
  85.     // Кол-во ребер содержащихся в кратчайшем пути = степень в которую нужно возвести матрицу весов
  86.     int k = N - 1;
  87.     // Бинарное возведение в степень
  88.     while(k > 0)
  89.     {
  90.         if(k % 2 == 1)
  91.         {
  92.             // Умножаем на матрицу весов - увеличиваем кол-во ребер в кратчайшем пути на одно
  93.             multiplyMatrix(matrix, W);
  94.             k--;
  95.         }
  96.         else
  97.         {
  98.             // Возводим матрицу в квадрат - увеличивая кол-во ребер в кратчайшем пути вдвое
  99.             squareMatrix(matrix);
  100.             k /= 2;
  101.         }
  102.     }
  103. }
  104.  
  105. int main()
  106. {
  107.     ios_base::sync_with_stdio(false);
  108.     cin.tie(0);
  109.     cout.tie(0);
  110.  
  111.     ReadWriter rw;
  112.     //Входные параметры
  113.     //N - количество вершин, M - количество ребер в графе
  114.     int N, M;
  115.     rw.read2Ints(N, M);
  116.  
  117.     //Вектор ребер, каждое ребро представлено 3-мя числами (А, В, W), где A и B - номера вершин, которые оно соединяет, и W - вес ребра
  118.     //Основной структурой выбран вектор, так как из него проще добавлять и удалять элементы (а такие операции могут понадобиться).
  119.     vector<Edge> edges;
  120.     rw.readEgdes(M, edges);
  121.  
  122.     vector<vector<int>> result(N);
  123.  
  124.     //Алгоритм решения задачи
  125.     solve(N, M, edges, result);
  126.  
  127.     rw.writeValues(result);
  128.  
  129.     return 0;
  130. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top