Luogu P1119 灾后重建

Sol:对于每个中转点K,需且仅需以此松弛一次

Key words:Floyd,本质活用

考题 路径数

题目描述:

Euphemia到一个N*N的药草田里采药,她从左上角的格子田(第一行,第一列)出发,要到达右下角(第N行,第N列)的格子田,每次她可以走到与当前格子有边相邻的格子去,但她不会走已经走过的格子,而且出于对美的要求,她走过的路径是关于 左下-右上 对角线对称的。由于地势不同,在每个格子田采药都会有一个疲劳度Tij,Euphemia想知道:有多少条合法路径,可以使得她采药的疲劳度最小。

输入格式:

多组数据。

每组数据第一行一个整数N,接下来N行,每行N个非零数字(1,2,3...9中一个),表示格子田的疲劳度。

当N=0,输入结束。

输出格式:

对于每组数据,输出一个整数表示答案,答案%1000000009。

样例输入:

2

1 1

1 1

3

1 1 1

1 1 1

2 1 1

0

样例输出:

2

3

数据范围与限制:

对于20%的数据满足N<=5。

对于另外20%的数据满足N<=40。

对于100%的数据满足N<=100,不超过50组数据。

Sol:对折,矩阵->图->最短路,dp统计最短路路径数
Key words:最短路,dp,最短路路径数

05-08 08:25