HUST 1408

http://acm.hust.edu.cn/problem/show/1408

[转] Floyd 算法原理

floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在），floyd算法加入了这个概念

A^k(i,j)：表示从i到j中途不经过索引比k大的点的最短路径。

这个限制的重要之处在于，它将最短路径的概念做了限制，使得该限制有机会满足迭代关系，这个迭代关系就在于研究：假设A^k(i,j)已知，是否可以借此推导出A^k-1(i,j)。

假设我现在要得到A^k(i,j)，而此时A^k(i,j)已知，那么我可以分两种情况来看待问题：1. A^k(i,j)沿途经过点k；2. A^k(i,j)不经过点k。如果经过点k，那么很显然，A^k(i,j) = A^k-1(i,k) + A^k-1(k,j)，为什么是A^k-1呢？因为对(i,k)和(k,j)，由于k本身就是源点（或者说终点），加上我们求的是A^k(i,j)，所以满足不经过比k大的点的条件限制，且已经不会经过点k，故得出了A^k-1这个值。那么遇到第二种情况，A^k(i,j)不经过点k时，由于没有经过点k，所以根据概念，可以得出A^k(i,j)=A^k-1(i,j)。现在，我们确信有且只有这两种情况---不是经过点k，就是不经过点k，没有第三种情况了，条件很完整，那么是选择哪一个呢？很简单，求的是最短路径，当然是哪个最短，求取哪个，故得出式子：

A^k(i,j) = min( A^k-1(i,j), A^k-1(i,k) + A^k-1(k,j) )

因此floyd的最外层循环：
for (k = 0; k < n; k++) ...
就是分别求出 A0(i,j), A1(i,j), ..., An(i,j)
我屡次写错floyd的程序，今天又写错一次。。尽管它很短，但原理真的很牛比。
只要知道了原理，就不会再写错了！

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<climits>
#include<queue>
#include<vector>
#include<map>
#include<sstream>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
//ifstream fin("input.txt");
//ofstream fout("output.txt");
//fin.close();
//fout.close();
ll dp[110][110];
ll L1, L2, L3, L4, C1, C2, C3, C4;
int n,m;
ll x[110];
const ll INF=999999999999;

void init()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j) dp[i][j]=0;
else if( 0<abs( x[j]-x[i])&&abs( x[j]-x[i])<=L1 ) dp[i][j]=C1;
else if( L1<abs(x[j]-x[i])&&abs(x[j]-x[i])<=L2 ) dp[i][j]=C2;
else if( L2<abs(x[j]-x[i])&&abs(x[j]-x[i])<=L3 ) dp[i][j]=C3;
else if(L3<abs(x[j]-x[i])&&abs(x[j]-x[i])<=L4 ) dp[i][j]=C4;
else dp[i][j]=INF;

}
}
}

void floyd()
{
int i,j,k;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}

}
int main()
{
int i,j,T,u,v,kase=0;
scanf("%d",&T);
while(T--)
{
printf("Case %d: ",++kase);
scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&L1, &L2, &L3, &L4, &C1,& C2, &C3, &C4);
// cout<<L1<<L2<<L3<<L4<<C1<<C2<<C3<<C4<<endl;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%lld",&x[i]);
}
init();
floyd();
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)
// cout<<dp[i][j]<<endl;
while(m--)
{
scanf("%d%d",&u,&v);
if(dp[u][v]>=INF)
printf("Station %d and station %d are not attainable. ",u,v);
else
printf("The minimum cost between station %d and station %d is %lld. ",u,v,dp[u][v]);

}

return 0;
}