2019银川网络赛 F Moving On Floyd 变形算法

问题 F: Moving On

时间限制: 10 Sec 内存限制: 128 MB
提交: 23 解决: 14
[提交] [状态] [命题人:admin]

题目描述

Firdaws and Fatinah are living in a country with n cities, numbered from 1 to n. Each city has a risk of kidnapping or robbery.
Firdaws’s home locates in the city u, and Fatinah’s home locates in the city v. Now you are asked to find the shortest path from the city u to the city v that does not pass through any other city with the risk of kidnapping or robbery higher than w, a threshold given by Firdaws.

输入

The input contains several test cases, and the first line is a positive integer T indicating the number of test cases which is up to 50.
For each test case, the first line contains two integers n (1≤n≤200) which is the number of cities, and q (1≤q≤2×104) which is the number of queries that will be given.The second line contains nn integers r1, r2, ⋯,rn indicating the risk of kidnapping or robbery in the city 1 to n respectively.Each of the following n lines contains n integers, the j-th one in the i-th line of which, denoted by di,j, is the distance from the city i to the city j.
Each of the following q lines gives an independent query with three integers u, v and w, which are described as above.
We guarantee that 1≤ri≤105, 1≤di,j≤105(i≠j), di,i=0 and di,j=dj,i.Besides, each query satisfies 1≤u,v≤n and 1≤w≤105.

输出

For each test case, output a line containing Case #x: at first, where x is the test case number starting from 1.Each of the following q lines contains an integer indicating the length of the shortest path of the corresponding query.

样例输入

复制样例数据

样例输出

Case #1:
0
1
3
0
1
2

题目大意：每次询问 u到v的最短距离，但是路程中不允许经过权值大于k的点，询问最短距离

题目思路：

比赛的时候用堆优化spfa 还是不过可能数据太大了，赛后看到题解之后恍然大悟，只能通过事先打表的方法，使之后询问的复杂度成为O1，我们考虑Floyd 算法的本质:

第一层：枚举通过哪个点可以得到的最短距离

第二层：枚举要求的起点

第三层：枚举要求的终点

所以我们考虑变形，先按权值从小到大排序，离散化排序也可以，这里我用的结构体排序，排完序之后就可以三层for枚举，根据Floyd的性质，第一层for枚举可以得到通过前几个点得到的最小路程则状态转移方程：

dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][r[j].id]+dp[k-1][r[j].id][i])

考虑前k个过度点，要么使用要么不使用就可以了。

AC代码：

#include<bits/stdc++.h>
#define ll long long
#include <stdio.h>
#include <algorithm>
#pragma GCC optimize(2)
using namespace std;
const int maxn=1e6+1000;
const ll INF=10000000000;
inline ll read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll  n,m;
int dp[222][222][222];
struct node{
    int id;
    ll w;
    bool friend operator<(node a,node b)
    {
        return a.w<b.w;
    }
}r[211];
int main()
{
    int T;scanf("%d",&T);
    int cas=0;
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=n;++i) {
            scanf("%lld",&r[i].w);
            r[i].id=i;
        }
        sort(r+1,r+1+n);
        for(int i=1;i<=n;i++)
            for(int k=1;k<=n;k++) scanf("%d",&dp[0][i][k]);
        for(int k=1; k<=n; ++k)
            for(int i=1;i<=n;++i)
                for(int j=1;j<=n;++j)
                    dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][r[k].id]+dp[k-1][r[k].id][j]);//dp[k][i][j]表示 添加(第1~k小的危险值的城市后)的 i->j 最短路
        printf("Case #%d:\n",++cas);
        while(m--)
        {
            ll u,v,ans;
            int pos=-1;
            scanf("%lld%lld%lld",&u,&v,&ans);
            for(int k=0;k<=n;k++)
                if(r[k].w<=ans) pos=k;
            printf("%lld\n",dp[pos][u][v]);
        }
    }
    return 0;
}

总结：

1.当n很小，并且询问多次两点之间最短路的时候可以使用Floyd算法

2.注意使用Floyd的任何变形