题目描述

给定一个 $n$ 个点 $m$ 条边的边带权简单连通无向图，在 $0$ 时刻你在点 $1$ 上。

假设当前是 $t$ 时刻，你在点 $v$ 上，你可以选择两种操作：

• 仍停留在点 $v$ 上，操作后到 $t+1$ 时刻。
• 选择一条边 $(a,b,w)$ 满足 $a=v$ 或 $b=v$，则你到这条边连接的另一个点上，操作后到 $t+w$ 时刻。

有 $k$ 条信息，每一条信息形如 $(t_i,v_i)$ 表示在 $t_i$ 时刻，点 $v_i$ 上会出现一只飞猪，其编号为 $i$，若该时刻你在 $v_i$ 上，则你捕获到了 $i$ 号飞猪。

现在你需要求出你能捕获到的飞猪数量的最大值。

输入格式

第一行为三个正整数 $n,m,k$。

接下来 $m$ 行每行三个正整数 $a_i,b_i,w_i$。

接下来 $k$ 行每行两个正整数 $t_i,v_i$。

输出格式

一行一个整数，为你能捕获到的飞猪数量的最大值。

样例 #1

样例输入 #1

2 1 5
1 2 2
1 2
2 2
3 2
5 1
7 2

样例输出 #1

4

提示

样例解释

最优方案如下：

$0$ 时刻，选择移动到节点 $2$，时间来到 $2$ 时刻。
$2$ 时刻，捕获到第 $2$ 只飞猪，选择停留在节点 $2$，时间来到 $3$ 时刻。
$3$ 时刻，捕获到第 $3$ 只飞猪，选择移动到节点 $1$，时间来到 $5$ 时刻。
$5$ 时刻，捕获到第 $4$ 只飞猪，选择移动到节点 $2$，时间来到 $7$ 时刻。
$7$ 时刻，捕获到第 $5$ 只飞猪。

数据范围

对于 $20\%$ 的数据，$n,m,k\le 7$。

对于 $100\%$ 的数据，$2\le n\le 200$，$1\le m\le \frac{n(n-1)}{2}$，$1\le k\le 5000$，$1\le a_i,b_i,v_i\le n$，$1\le w_i\le 1000$，$1\le t_i\le 10^9$。

思路

那么一眼 $DP$，但是还是想了一个小时的转移才想明白是 $floyd$ + 线性$DP$ 。

先用 $floyd$ 算出两点之间的最短距离（时间成本作边权），然后读入所有猪的信息，并按时间进行升序排序，定义状态 $f[i][j]$ 为前 $i$ 头猪，最后选中的猪是第$j$头猪的最大捕获数量。则可以推得转移为
$$f[i][j] = \left\\{ \begin{array}{ll} f[i - 1][j] &,i \ne j \\\ f[i][k] + 1 &,i = j \ and \ k \in [0,i) \ and \ d[i][k] + pig[k].time \le pig[i].time \end{array} \right.$$
$pig[0]$ 用来存起点（在 $0$ 时刻你在点 $1$ ）的信息。

可以发现 $i$ 所在的第一维可以略去。最终的答案就是所有状态 $f[1]$ ~ $f[K]$ 中的一个最大值。

#include <iostream>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int (a) = (b) ; (a) < (c) ; ++(a))
using namespace std;
using ll = long long ;
using pii = pair<int,int> ;
char CH,NUM[40];bool F;int LEN;
template <typename T>
inline void R(T &x){
    x = 0,F = 0,CH = getchar();
    while (CH < '0' || CH > '9' ){if (CH == '-') F = 1;CH = getchar();}
    while (CH >= '0'&& CH <= '9' ){x = (x << 3) + (x << 1) + (CH & 15) ; CH = getchar() ;}
    if (F) x = -x ;
}
template <typename T>
inline void W(T x) {
    if (!x){ putchar('0'); return ;} LEN = 0; 
    if (x < 0) putchar('-'), x = -x; 
    while(x) NUM[++LEN] = (x - x / 10 * 10 ) + 48, x /= 10;
    while(LEN) putchar(NUM[LEN--]); 
}
const int maxn = 205 ;
int d[maxn][maxn],n,m,K;
pii pig[5050];
int f[maxn];
int main(){
    memset(d,0x3f,sizeof d);
    int u,v,w;
    R(n),R(m),R(K);
    rep(i,1,n + 1) d[i][i] = 0 ;
    rep(i,1,m + 1){
        R(u),R(v),R(w);
        d[u][v] = d[v][u] = min(d[u][v],w);
    }
    rep(k,1,n + 1)
        rep(i,1,n + 1)
            rep(j,1,n + 1)
                d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
    rep(i,1,K + 1) R(pig[i].first),R(pig[i].second) ;   // first 是时间，second 是所在点
    sort(pig + 1,pig + K + 1);
    pig[0] = {0,1};
    int res = 0 ;
    rep(i,1,K + 1){
        u = pig[i].second ;
        rep(j,0,i)  {
            if (d[u][pig[j].second] + pig[j].first <= pig[i].first)
                f[i] = max(f[i],f[j] + 1) ;
        }
        res = max(res,f[i]);
    }
    W(res);
    return 0;
}