[TIOJ] 1146 . 1.城市道路連通網

題目連結:http://tioj.infor.org/problems/1146

---

這題其實跟[TIOJ]1428很像，只是他不能快速冪，而是要$O(n)$做矩陣乘法，然後每次做完後就把答案加起來

#include <stdio.h>
#include <algorithm>

int size;

auto graph = new int[35][35];
auto temp = new int[35][35];

inline void matrixTimes(int [][35], int[][35], int[][35]);

int main(){
	scanf("%d",&size);
	for(int i=0;i<size;i++){
		char inp[35];
		scanf("%s",inp);
		for(int j=0;j<size;j++){
			temp[i][j]=i==j;
			graph[i][j]=inp[j]-'0';
		}
	}
	int x,y,n,ans=0;
	scanf("%d\n%d\n%d",&x,&y,&n);
	while(n){
		auto tp = new int[35][35];
		matrixTimes(graph,temp,tp);
		std::swap(tp,temp);
		ans+=temp[x-1][y-1];
		n--;
	}
	printf("%d",ans);
	return 0;
}
inline void matrixTimes(int a[][35], int b[][35], int c[][35]){
	for(int i=0;i<size;i++){
		for(int j=0;j<size;j++){
			c[i][j]=0;
			for(int k=0;k<size;k++){
				c[i][j] += a[i][k]*b[k][j];
			}
		}
	}
}