题意：一个无向图，求从一个顶点到另一个顶点的恰好经过k条边的最短路径，可能有自环，无重边。
分析：这个题其实就是矩阵乘法，用了dp的思想，dp[k][i][j]代表恰好经过k条边的i到j的最短路，那么dp[k][i][j]=min{dp[k-1][i][p]+g[p][j]}（其中g是原图）。可以用矩阵乘法来做，因为对于dp[k-1][i][j]来说，只要乘以一次原图矩阵，就相当于做了一次转移，得到的就是dp[k][][]矩阵。我想说这个题除了状态设计和floyd稍微沾了一点边之外，其他一点关系都没有了，竟然看到网上好多人用写floyd的循环顺序来写这个题，真是令人费解，这个题只是改了矩阵乘法的最内层，改变了矩阵乘法的运算规则，和floyd真的没关系啊！！！
另外，矩阵乘法的规则和在图中求一个点到另一个点的恰好经过k条边的方法数的规则是一样的，二者的状态转移方程也是一样的，所以矩阵乘法不需要经过任何修改就能做这种求恰好经过k条边的方法数的题，而不用像这个题还得做些修改。这些题都需要注意初始化的东西，尤其是g[i][i]，就是定义一个点到本身的权值，本题需要定义为INF，因为如果题目不给自环边的话，那么本身到本身应该认为是不可达的，距离是无穷大的，千万不能定义为0；而求恰好经过k条边的方法数的题的话，应该初始化为0，因为该点到本身应该是有0种方法恰好经过一条边到达（如果没有自环，原图看做是恰好经过一条边从i到j的方法数）。一旦设置好了初始矩阵，神马存在自环啊或者其它环啊之类的问题都不需要我们考虑了，矩阵乘法都帮我们搞定。
这个题我还学到了个东西，就是求矩阵a的b次幂的刚刚进入函数部分的写法，我以前的写法都是把ans设置为单位矩阵，然后再进入循环做快速幂。今天突然看到有个人的代码，猛地反应过来可以直接设置ans等于传入的矩阵a，然后把幂次减一直接进入循环啊，不需要写设置单位矩阵部分的代码了，以前咋没怎么想呢。。。二了
/*
POJ 3613
code by heifrank
*/
#include <cstdio>
#include <map>
using namespace std;
const int MV = 205;
const int INF = 0x7fffffff;
int n;
map<int, int> M;
struct mat{
int ele[MV][MV];
mat(){init();}
void init(){
for(int i=0; i<MV; i++)for(int j=i; j<MV; j++)
ele[i][j] = ele[j][i] = INF;
}
mat operator*(const mat& ext){
mat ans;
for(int i=1; i<=n; i++)for(int j=1; j<=n; j++){
for(int k=1; k<=n; k++){
if(ele[i][k] == INF || ext.ele[k][j] == INF)continue;
ans.ele[i][j] = min(ans.ele[i][j], ele[i][k]+ext.ele[k][j]);
}
}
return ans;
}
}a;
mat get(mat a, int b){
mat ans = a;
b--;
while(b){
if(b&1)ans = ans*a;
a = a*a;
b >>= 1;
}
return ans;
}
int main(){
int T, m, st, ed, u, v, w;
scanf("%d%d%d%d", &T, &m, &st, &ed);
a.init();
for(int i=1; i<=m; i++){
scanf("%d%d%d", &w, &u, &v);
if(!M[u])M[u] = ++n;
if(!M[v])M[v] = ++n;
u = M[u], v = M[v];
a.ele[u][v] = a.ele[v][u] = min(a.ele[u][v], w);
}
mat ans = get(a, T);
printf("%d\n", ans.ele[M[st]][M[ed]]);
return 0;
}
Comments