Codevs 1077 多源最短路（ Floyd水 ）

---

**链接：****传送门 **

思路：裸 Floyd

---

/*************************************************************************
    > File Name: codevs1077.cpp
    > Author:    WArobot 
    > Blog:      http://www.cnblogs.com/WArobot/ 
    > Created Time: 2017年06月14日 星期三 20时20分57秒
 ************************************************************************/

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

const int MAX_N = 120;
int dis[MAX_N][MAX_N];
int n , st , ed , Q;

void floyd(){
	for(int k = 0 ; k < n ; k++){
		for(int i = 0 ; i < n ; i++){
			for(int j = 0 ; j < n ; j++){
				dis[i][j] = min( dis[i][j] , dis[i][k] + dis[k][j] );
			}
		}
	}
}
int main(){
	while(~scanf("%d",&n)){
		for(int i = 0 ; i < n ; i++)
			for(int j = 0 ; j < n ; j++)
				scanf("%d",&dis[i][j]);
		scanf("%d",&Q);
		floyd();
		while(Q--){
			scanf("%d%d",&st,&ed);
			printf("%d
",dis[st-1][ed-1]);
		}
	}
	return 0;
}