考察:Floyd+矩阵快速幂
思路:
前面讲过Floyd算法的第一层循环是i~j的最短路,经过1~k的结点.在这里我们将Floyd的dp状态表示f[k,i,j].
假设i经过a条边到达S, f[k,i,j] = f[a,i,S]+f[k-a,S,j] 我们可以发现前a条边的路径与后面的路径不相干,所以我们可以这么写.
然后就可以发现k可以被分成1条,2条,4条...符合结合律我们可以用矩阵快速幂.
1 #include <iostream>
2 #include <cstring>
3 #include <map>
4 using namespace std;
5 const int N = 1010,M = 210;
6 map<int,int> mp;
7 int n,T,S,E,idx,g[M][M],res[M][M],tmp[M][M];
8 int get(int x)
9 {
10 if(!mp.count(x)) mp[x] = ++idx;
11 return mp[x];
12 }
13 void mul(int res[][M],int g[][M])
14 {
15 memset(tmp,0x3f,sizeof tmp);
16 for(int k=1;k<=idx;k++)
17 for(int i=1;i<=idx;i++)
18 for(int j=1;j<=idx;j++)
19 tmp[i][j] = min(res[i][k]+g[k][j],tmp[i][j]);
20 memcpy(res,tmp,sizeof tmp);
21 }
22 void mulself(int g[][M])
23 {
24 memset(tmp,0x3f,sizeof tmp);
25 for(int k=1;k<=idx;k++)
26 for(int i=1;i<=idx;i++)
27 for(int j=1;j<=idx;j++)
28 tmp[i][j] = min(g[i][k]+g[k][j],tmp[i][j]);
29 memcpy(g,tmp,sizeof tmp);
30 }
31 int main()
32 {
33 scanf("%d%d%d%d",&n,&T,&S,&E);
34 memset(g,0x3f,sizeof g); memset(res,0x3f,sizeof res);
35 while(T--)
36 {
37 int a,b,w; scanf("%d%d%d",&w,&a,&b);
38 int pa = get(a),pb =get(b);
39 g[pa][pb] = g[pb][pa] = min(g[pb][pa],w);
40 }
41 S = get(S),E = get(E);
42 for(int i=1;i<=idx;i++) res[i][i] = 0;
43 memcpy(res,g,sizeof g);
44 n--;
45 while(n)
46 {
47 if(n&1) mul(res,g);
48 mulself(g);
49 n>>=1;
50 }
51 printf("%d\n",res[S][E]);
52 return 0;
53 }