http://poj.org/problem?id=3613

s->t上经过k条边的最短路

先把1000范围的点离散化到200中,然后使用最短路可以使用floyd,由于求的是经过k条路的最短路,跑k-1次“floyd”即可(使用矩阵快速幂的思想)。

把给定的图转为邻接矩阵,即A(i,j)=1当且仅当存在一条边i->j。令C=A*A,那么C(i,j)=ΣA(i,k)*A(k,j),实际上就等于从点i到点j恰好经过2条边的路径数(枚举k为中转点)。类似地,C*A的第i行第j列就表示从i到j经过3条边的路径数。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define clr0(x) memset(x,0,sizeof(x))
#define clr1(x) memset(x,-1,sizeof(x))
#define eps 1e-9
const double pi = acos(-1.0);
typedef long long LL;
const int inf = 0x7fffffff;
const int maxn = 205;
map <int , int> mp;
int k,m,st,en;
int n;//floyd矩阵大小
struct Matrix{
int mat[maxn][maxn];
void init(){
for(int i = 0;i < maxn;++i)
for(int j = 0;j < maxn;++j)
mat[i][j] = inf;
}
};
Matrix ans,tmp,_tmp;
void copy(Matrix &b,Matrix a){
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j)
b.mat[i][j] = a.mat[i][j];
}
void floyd(Matrix &a,Matrix b,Matrix c){
a.init();
for(int k = 1;k <= n;++k)
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j){
if(b.mat[i][k] == inf || c.mat[k][j] == inf)
continue;
if(a.mat[i][j] > b.mat[i][k]+c.mat[k][j])
a.mat[i][j] = b.mat[i][k]+c.mat[k][j];
}
}
int has[1005];
void init()
{
n = 0;
clr0(has);
ans.init(),tmp.init();
for(int i = 0;i < maxn;++i)
ans.mat[i][i] = 0;
int u,v,w;
for(int i = 0;i < m;++i){
RD3(w,u,v);
if(has[u] == 0)
has[u] = ++n;
if(has[v] == 0)
has[v] = ++n;
if(tmp.mat[has[u]][has[v]] > w)
tmp.mat[has[v]][has[u]] = tmp.mat[has[u]][has[v]] = w;
}
}
void work()
{
while(k){
if(k&1){
copy(_tmp,ans);
floyd(ans,_tmp,tmp);
}
copy(_tmp,tmp);
floyd(tmp,_tmp,_tmp);
k>>=1;
}
printf("%d\n",ans.mat[has[st]][has[en]]);
}
int main()
{
while(~RD2(k,m)){
RD2(st,en);
init();
work();
}
return 0;
}
05-11 09:39