弗洛里达（Floyd）算法求图的最短路径

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

#define OFFSET 1

int main() {
    int N, M, ST;
    while (cin >> N >> M) {
        vector<vector<int>> vvi(N, vector<int>(N, 0));
        for (; M--;) {
            int temp_start, temp_end, temp_dist;
            cin >> temp_start >> temp_end >> temp_dist;
            vvi[temp_start - OFFSET][temp_end - OFFSET] = temp_dist;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j || vvi[i][j] == 0)
                    continue;
                for (int k = 0; k < N; k++) {
                    if (i == k || j == k || vvi[k][i] == 0)
                        continue;
                    if (vvi[k][j] == 0 || vvi[k][i] + vvi[i][j] < vvi[k][j])
                        vvi[k][j] = vvi[k][i] + vvi[i][j];
                }
            }
        }
        // output the result as follows:
        for (ST = 1; ST <= N; ST++) {
            cout << "start position: " << ST << endl;
            for (int i = 0; i < N; i++) {
                if (i + 1 == ST)
                    continue;
                else if (vvi[ST - OFFSET][i] == 0)
                    cout << "there is no path from " << ST << " to " << i + 1 << endl;
                else
                    cout << "the shortest distance from " << ST << " to " << i + 1 << " is " << vvi[ST - OFFSET][i] << endl;
            }
            cout << endl;
        }
    }
    return 0;
}

/*
example:
7 10
1 2 8
1 3 5
1 4 3
2 5 3
3 2 2
3 6 5
3 7 2
6 4 9
7 5 6
7 6 2
*/

执行结果：
7 10
1 2 8
1 3 5
1 4 3
2 5 3
3 2 2
3 6 5
3 7 2
6 4 9
7 5 6
7 6 2
start position: 1
the shortest distance from 1 to 2 is 7
the shortest distance from 1 to 3 is 5
the shortest distance from 1 to 4 is 3
the shortest distance from 1 to 5 is 10
the shortest distance from 1 to 6 is 9
the shortest distance from 1 to 7 is 7

start position: 2
there is no path from 2 to 1
there is no path from 2 to 3
there is no path from 2 to 4
the shortest distance from 2 to 5 is 3
there is no path from 2 to 6
there is no path from 2 to 7

start position: 3
there is no path from 3 to 1
the shortest distance from 3 to 2 is 2
the shortest distance from 3 to 4 is 13
the shortest distance from 3 to 5 is 5
the shortest distance from 3 to 6 is 4
the shortest distance from 3 to 7 is 2

start position: 4
there is no path from 4 to 1
there is no path from 4 to 2
there is no path from 4 to 3
there is no path from 4 to 5
there is no path from 4 to 6
there is no path from 4 to 7

start position: 5
there is no path from 5 to 1
there is no path from 5 to 2
there is no path from 5 to 3
there is no path from 5 to 4
there is no path from 5 to 6
there is no path from 5 to 7

start position: 6
there is no path from 6 to 1
there is no path from 6 to 2
there is no path from 6 to 3
the shortest distance from 6 to 4 is 9
there is no path from 6 to 5
there is no path from 6 to 7

start position: 7
there is no path from 7 to 1
there is no path from 7 to 2
there is no path from 7 to 3
the shortest distance from 7 to 4 is 11
the shortest distance from 7 to 5 is 6
the shortest distance from 7 to 6 is 2