查看原题请戳这里
首先，我们要明确这里的最短路是在经过n条路径的前提下的最短路，因为这是无向图，所以一定有解。
我们先来看朴素的Floyd的代码：
1
2
3
4
| for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
f[i][j] = min(f[i][j],f[i][k] + f[k][j]);
|
其中，我们每次都是枚举k并用ta去当中转点去更新每一个i->j的最短路。
那么，当k等于n/2时这段代码完成了什么呢？
那就是我们尝试了用[1,n/2]的点去更新最短路，我们可以发现，这样得到的最短路最多包含k+1条路径。
为什么是最多k+1条呢？
因为我们每次用k去尝试更新i->j的最短路是不一定成功（即f[i][j]<=f[i][k]+f[k][j]）
所以我们可以用Floyd+dp+倍增去切掉这道题
我们再来看一下矩阵乘法的代码：
1
2
3
4
| for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
c[i][j] = c[i][j] + a[i][k] * b[k][j];
|
是不是和Floyd的代码有点相似？
因为我们要求的是最短路，所以我们要对这个矩阵乘法魔改一下：
1
2
3
4
5
| memset(c,0x7f,sizeof(c));
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
c[i][j] = min(c[i][j],a[i][k] + a[k][j]);
|
是不是和Floyd越来越相似了……
但是在这里，c[i][j]的初值为INF，所以我们每次枚举k都会选择一条边去更新最短路，所以如果我们用邻接矩阵map（不是STL的那个map）去存边，那么map的n次方存的就是经过n条边的最短路。
code:
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
76
77
78
79
80
81
82
83
84
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define qwq printf("qwq\n");
using namespace std;
long long read()
{
register long long x = 0,f = 1;register char ch;
ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
return x * f;
}
long long n,m,t,sta,End,cnt,siz,u,d[100005];
struct edge{
int fro,to,l;
}e[100005];
struct juzhen{
long long a[105][105];
juzhen operator * (const juzhen &x) const
{
juzhen c;
memset(c.a,0x7f,sizeof(c.a));
for(int k = 1; k <= siz; k++)
for(int i = 1; i <= siz; i++)
for(int j = 1; j <= siz; j++)
c.a[i][j] = min(c.a[i][j],a[i][k]+x.a[k][j]);
return c;
}
}ans,map;
void ksm(int b)
{
while(b > 0)
{
if(b & 1) ans = ans * map;
map = map * map;
b >>= 1;
}
}
bool cmp(int a,int b){return a < b;}
int main()
{
n = read(); m = read(); sta = read(); End = read();
for(int i = 1; i <= m; i++)
{
e[i].l = read(); e[i].fro = read(); e[i].to = read();
d[++cnt] = e[i].fro; d[++cnt] = e[i].to;
}
sort(d + 1, d + cnt + 1, cmp);
siz = unique(d + 1, d + cnt + 1) - d - 1;
for(int i = 1; i <= siz; i++)
for(int j = 1; j <= siz; j++)
map.a[i][j] = INF;
for(int i = 1; i <= m; i++)
{
e[i].fro = lower_bound(d + 1, d + siz + 1, e[i].fro) - d;
e[i].to = lower_bound(d + 1, d + siz + 1, e[i].to) - d;
map.a[e[i].fro][e[i].to] = e[i].l;
map.a[e[i].to][e[i].fro] = e[i].l;
}
sta = lower_bound(d + 1, d + siz + 1, sta) - d;
End = lower_bound(d + 1, d + siz + 1, End) - d;
for(int i = 1; i <= siz; i++)
for(int j = 1; j <= siz; j++)
ans.a[i][j] = map.a[i][j];
ksm(n - 1);
printf("%d\n",ans.a[sta][End]);
return 0;
}
|
