$K$ 的数据范围异常小，引导我们往状压上思考。
设 $dp_{st,y}$ 表示已经包含 $1\sim k$ 以及 $x$ ，与 $y$ 建立联系的最小花费，其中 $1\sim k$ 以及 $x$ 可以用 $2^{k + 1}$ 种状态来表示。枚举 $st$ 中包含 $x$，存在以下两种方式：
- 对于同一个 $y$，通过子集枚举来转移：
- 对于不同的 $y$，需要一个中间点 $k$，这就想到可以通过最短路的方式进行状态的更新：
最后的时间复杂度为 $O(n^2 3^k + n^2 2^k \log n)$，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| #include <bits/stdc++.h>
#define init(x) memset (x,INF,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair <ll,int>
using namespace std;
const int MAX = 85;
const int MOD = 1e9 + 7;
inline int read ();
int n,m,q,c[MAX][MAX],vis[MAX];ll ans[MAX][MAX],dp[1 << 9][MAX];
void dijkstra (ll *dis);
void solve (int x);
int main ()
{
n = read ();m = read ();
for (int i = 0;i < n;++i)
for (int j = 0;j < n;++j) c[i][j] = read ();
for (int i = 0;i < n;++i) solve (i);
q = read ();
while (q--)
{
int x = read (),y = read ();
printf ("%lld\n",ans[--x][--y]);
}
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
void solve (int x)
{
init (dp);
dp[1 << m][x] = 0;
for (int i = 0;i < m;++i) dp[1 << i][i] = 0;
for (int S = 0;S < (1 << (m + 1));++S)
{
for (int i = 0;i < n;++i)
for (int T = S & (S - 1);T;T = (T - 1) & S)
dp[S][i] = min (dp[S][i],dp[T][i] + dp[T ^ S][i]);
dijkstra (dp[S]);
}
for (int i = 0;i < n;++i) ans[x][i] = dp[(1 << (m + 1)) - 1][i];
}
void dijkstra (ll *dis)
{
priority_queue <pii> q;
for (int i = 0;i < n;++i) q.push ({-dis[i],i}),vis[i] = 0;
while (!q.empty ())
{
int u = q.top ().second;q.pop ();
if (vis[u]) continue;
vis[u] = 1;
for (int v = 0;v < n;++v)
if (dis[v] > dis[u] + c[u][v]) dis[v] = dis[u] + c[u][v],q.push ({-dis[v],v});
}
}
|
