- /*--------------------denghui-2015.11.16---------------------------*/
- /*input: a int number n, means the number of node on the graph
- n(row)*n(col) (int) , means the graph matrix
- s(int), means the number of test data
- s(row)*2(col) (int), means start and end
- like this:
- 4
- 0 2 10 10000
- 2 0 7 3
- 10 7 0 6
- 1000 3 6 0
- 2
- 0 2
- 3 0
- */
- #include <iostream>
- using namespace std;
- #define MAX 30
- int readdata(int Graph[][MAX]);
- void search(int Graph[][MAX], int Path[][MAX], int n);
- void display(int Path[][MAX], int n);
- void putout(int Path[][MAX], int start, int end);
- int main()
- {
- int Graph[MAX][MAX];
- int n = readdata(Graph);
- int Path[MAX][MAX];
- search(Graph, Path, n);
- display(Path, n);
- return 0;
- }
- int readdata(int Graph[][MAX])
- {
- int n;
- cin >> n;
- int i, j;
- for (i = 0; i < n; ++i) {
- for (j = 0; j < n; ++j) {
- cin >> Graph[i][j];
- }
- }
- return n;
- }
- void search(int Graph[][MAX], int Path[][MAX], int n)
- {
- int point[MAX][MAX];
- int i, j, k;
- for (i = 0; i < n; ++i) { // init
- for (j = 0; j < n; ++j) {
- point[i][j] = Graph[i][j];
- Path[i][j] = -1;
- }
- }
- for (i = 0; i < n; ++i) {
- for (j = 0; j < n; ++j) {
- for (k = 0; k < n; ++k) {
- if (point[j][i] + point[i][k] < point[j][k]) {
- point[j][k] = point[j][i] + point[i][k];
- Path[j][k] = i;
- }
- }
- }
- }
- }
- void display(int Path[][MAX], int n)
- {
- int start, end, s;
- cin >> s;
- while (s > 0) {
- s--;
- cin >> start >> end;
- putout(Path, start, end);
- cout << end << endl;
- }
- }
- void putout(int Path[][MAX], int start, int end)
- {
- if (Path[start][end] == -1) {
- cout << start << endl;
- } else {
- putout(Path, start, Path[start][end]);
- putout(Path, Path[start][end], end);
- }
- }
- //end
- /*=============================Denghui=================================*/
- //该片段来自于http://www.codesnippet.cn/detail/1412201514226.html
来源: http://www.codesnippet.cn/detail/1412201514226.html