Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #define INF 1000000000
- const int MAX_N = 100;
- int g[MAX_N][MAX_N];
- int main() {
- #ifndef ONLINE_JUDGE
- freopen("/home/nikita/CLionProjects/Algorithms/Contest3/B.txt", "r", stdin);
- #endif
- int n;
- std::cin >> n;
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- int weight;
- std::cin >> weight;
- if (i == j) {
- g[i][i] = 0;
- } else if (weight == 0) {
- g[i][j] = INF;
- } else {
- g[i][j] = weight;
- }
- }
- }
- for (int k = 0; k < n; ++k) {
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- if (g[i][k] < INF && g[k][j] < INF) {
- g[i][j] = std::min(g[i][j], g[i][k] + g[k][j]);
- }
- }
- }
- }
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- for (int t = 0; t < n; ++t) {
- if (g[i][t] < INF && g[t][t] < 0 && g[t][j] < INF) {
- g[i][j] = -INF;
- }
- }
- }
- }
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- int value = 1;
- if (g[i][j] == INF) {
- value = 0;
- } else if (g[i][j] == -INF) {
- value = 2;
- }
- std::cout << value << " ";
- }
- std::cout << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement