题目#

跑路#

小 A 的工作不仅繁琐，更有苛刻的规定，要求小 A 每天早上在 $6:00$ 之前到达公司，否则这个月工资清零。可是小 A 偏偏又有赖床的坏毛病。于是为了保住自己的工资，小 A 买了一个空间跑路器，每秒钟可以跑 $2^k$ 千米（ $k$ 是任意自然数）。当然，这个机器是用 longint 存的，所以总跑路长度不能超过 maxlongint 千米。小 A 的家到公司的路可以看做一个有向图，小 A 家为点 $1$ ，公司为点 $n$ ，每条边长度均为一千米。小 A 想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证 $1$ 到 $n$ 至少有一条路径。

$100\%$ 的数据满足 $2\leq n \leq 50$ ， $m \leq 10 ^ 4$ ，最优解路径长度 $\leq$ maxlongint。

题解#

这是一种很奇妙的dp——图上dp

然而显然这并不是dag，所以考虑新方法

由于跑路机每次只能走 $2^k km$ ，所以设f[i][u][v]表示是否存在从u到v的长度为 $2^i$ 的路径

转移的话 $2^i$ 可以从 $2^{i-1}$ 转移来

看代码吧

问题#

floyd写炸了！

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
int read()
6
{
7
  int f = 1, x = 0;
8
  char ch = getchar();
9
  while(ch < '0' || ch > '9')
10
  {
11
    if(ch == '-') f = -1;
12
    ch = getchar();
13
  }
14

15
  while(ch >= '0' && ch <= '9')
16
  {
17
    x = x * 10 + ch - '0';
18
    ch = getchar();
19
  }
20
  return f * x;
21
}
22

23
const int N = 55;
24
int n, m;
25
bool f[N][N][35];
26
bool G_new[N][N];
27
int dis[N][N];
28

29

30
int main()
31
{
32
  n = read(), m = read();
33
  int u, v;
34
  for(int i = 1;i <= m;i++)
35
  {
36
    u = read(), v = read();
37
    f[u][v][0] = 1;
38
  }
39

40
  for(int k = 1;k <= 33;k++)
41
  {
42
    for(int t/*中转点*/ = 1;t <= n;t++)
43
      for(int i = 1;i <= n;i++)
44
      {
45
        for(int j = 1;j <= n;j++)
46
        {
47
          f[i][j][k] |= (f[i][t][k - 1] & f[t][j][k - 1]);
48
        }
49
      }
50
  }
51
  memset(dis, 0x3f, sizeof dis);
52

53
  for(int k = 0;k <= 33;k++)
54
  {
55
    for(int i = 1;i <= n;i++)
56
    {
57
      for(int j = 1;j <= n;j++)
58
      {
59
        G_new[i][j] |= f[i][j][k];
60
      }
61
    }
62
  }
63

64
  for(int i = 1;i <= n;i++)
65
  {
66
    for(int j = 1;j <= n;j++)
67
    {
68
      if(G_new[i][j])
69
        dis[i][j] = 1;
70
    }
71
  }
72

73
  for(int k = 1;k <= n;k++)
74
  {
75
    for(int i = 1;i <= n;i++)
76
    {
77
      for(int j = 1;j <= n;j++)
78
      {
79
        if(k == i || k == j || i == j) continue;
80
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
81
      }
82
    }
83
  }
84

85
  cout << dis[1][n];
86
  return 0;
87
}

P1613 跑路

https://blog.histcat.top/posts/p1613/

作者

Histcat

发布于

2023-09-26

许可协议

CC BY-NC-SA 4.0

P1352 没有上司的舞会

P1896 [SCOI2005] 互不侵犯