Gym102222G-Floyd

题目链接

Gym102222G

思路

首先我们来弄清楚floyd算法，普通的floyd算法我们只用来算最短路，所以通常都省略了一维空间。

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

上面展示的代码，就是我们通常用的Floyd，但是我们的数组是二维的，但是循环却有3个，那么第三维是什么？为什么被省略了？
上述代码针对多源多终点的问题写的代码。dis[i][j]的意义是$d_{ij}$的最短路,而k指的是必定经过第k个点的最短路，也就是dis[i][k]+dis[k][j]。
假设此时k=5，那么前4个点dis[i][j]就已经确定了，此时加入第五个点，判断是否有最新的路需要更新，这就是floyd的全部。
现在我们回顾上面的问题，第三维是什么？就是范围，前K点。为什么通常被忽略了，因为简单的最短路全部的路都可以走。
实际的三维是dis[k][i][j]表示前k个点之前的i~j的最短路，更新代码如下

for(int k=1;k<=n;k++)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dis[k][i][j]=min(dis[k-1][i][j],dis[k-1][i][k]+[k-1]dis[k][j]);
		}
	}
}

那么针对这一道题，我们可以对点从小到大排序后，然后再取能够到达最远的点，然后直接输出即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e2+10;
int dp[N][N][N];
int mp[N][N];
int Hash[N];
int n,q,u,v,w;
struct node
{
	int id,num;
}a[N];
void floyd()
{
	for(int k=1;k<=n;k++)
	{
		int id = a[k].id;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				dp[k][i][j]=min(dp[k-1][i][id]+dp[k-1][id][j],dp[k-1][i][j]);
			}
		}
	}
}
int cmp(node a,node b)
{
	return a.num<b.num;
}
int main()
{   int  t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
    memset(dp,0x3f3f,sizeof(dp));
    printf("Case #%d:\n",cas);
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d",&a[i].num),a[i].id=i;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&dp[0][i][j]);
		}
	}
	floyd();
	while(q--)
	{
		scanf("%d %d %d",&u,&v,&w);
		int o;
		for(o=1;o<=n;o++)if(a[o].num>w)break;
		printf("%d\n",dp[o-1][u][v]);
	}
    }
}