bzoj1706[usaco2007 Nov]relays 奶牛接力跑*

bzoj1706[usaco2007 Nov]relays 奶牛接力跑

题意：

无向图，求刚好经过n条边的最小距离。边数≤100，n≤1000000。

题解：

边数≤100，说明点数不超过200。故可以用floyd。但要用一点技巧，即倍增floyd：定义最短路矩阵之间的乘法为对它们做floyd，则最后答案矩阵为初始边矩阵的“n次幂”，同时这种乘法满足结合律，故可以用快速幂使得复杂度降低。本弱遇到了莫名其妙的问题，快速幂一写成递归形式就爆栈，样例都过不去，写成二进制拆分形式才能不RE。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <map>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 210
 7 #define ll long long
 8 #define INF 10000000000000000
 9 using namespace std;
10 
11 inline int read(){
12     char ch=getchar(); int f=1,x=0;
13     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
14     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
15     return f*x;
16 }
17 int tot,n,t,s,e; map<int,int>mp;
18 struct mat{
19     ll dis[maxn][maxn];
20 }f[25],ans;
21 mat operator * (mat a,mat b){
22     mat c; inc(i,1,n)inc(j,1,n)c.dis[i][j]=INF;
23     inc(k,1,n)
24         inc(i,1,n)
25             inc(j,1,n)c.dis[i][j]=min(c.dis[i][j],a.dis[i][k]+b.dis[k][j]);
26     return c;
27 }
28 int getnum(int x){
29     int y=mp[x]; if(!y){mp[x]=++n; return n;}else return y;
30 }
31 int main(){
32     tot=read(); t=read(); s=getnum(read()); e=getnum(read());
33     inc(i,1,t){
34         int x=read(),y=getnum(read()),z=getnum(read()); f[0].dis[y][z]=x; f[0].dis[z][y]=x;
35     }
36     inc(i,1,n)inc(j,1,n)if(!f[0].dis[i][j])f[0].dis[i][j]=INF;
37     for(int i=1;(1<<i)<=tot;i++)f[i]=f[i-1]*f[i-1]; bool fl=0;
38     for(int i=0;(1<<i)<=tot;i++)if(tot&(1<<i)){if(!fl)ans=f[i],fl=1;else ans=ans*f[i];}
39     printf("%lld",ans.dis[s][e]); return 0;
40 }

20160929