<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
::-webkit-scrollbar {
width: 10px;
}
::-webkit-scrollbar-track {
background: transparent;
}
::-webkit-scrollbar-thumb {
background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
border-radius: 3px;
}
::-webkit-scrollbar-thumb:hover {
background: linear-gradient(180deg, #2BE8CF95 0%, #2B83E895 100%);
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}

</style>
###### tags: `Algorithm_Lab`

# Floyd Warshall Algorithm 結報
## OJ AC截圖

## Code

#include <bits/stdc++.h>
#define INF 2000000
using namespace std;

bool Floyd_Warshall(vector<vector<int>> &distance, int &starSystem) {
    for (int k = 0; k < starSystem; ++k)
        for (int i = 0; i < starSystem; ++i)
            for (int j = 0; j < starSystem; ++j)
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j]);

    for (int i = 0; i < starSystem; ++i)
        if (distance[i][i] < 0) return true;
    return false;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int Case;
    cin >> Case;
    while (Case--) {
        int starSystem, wormhole;
        cin >> starSystem >> wormhole;
        vector<vector<int>> distance(starSystem, vector<int>(starSystem, INF));
        for (int i = 0; i < starSystem; ++i)
            distance[i][i] = 0;
        for (int i = 0; i < wormhole; ++i) {
            int x, y, t;
            cin >> x >> y >> t;
            distance[x][y] = min(t, distance[x][y]);
        }
        if (Floyd_Warshall(distance, starSystem))
            cout << "possible\n";
        else
            cout << "not possible\n";
    }
}

### Assume $n$ is star system's number.
## 空間複雜度分析
* starSystem($n^2$)
* i, i, k, i, j, i(6)
$Total: n^2 + 2$
$O(n^2)$

## 時間複雜度分析

### Best Case && Worst Case
* 不論輸入為何，三層巢狀迴圈都不會提前停止。
* $O(n^3)$

## DATE

2023/03/29