BZOJ 1706

时间:2024-05-20 10:36:38

题解:

倍增+floyd

首先这题比较容易想到是把每个点拆点做dij

但是这样复杂度是knlogn的

这道题的k较大,所以不行

我们考虑到每走一步,其实就是在进行一次floyd

而这个可以看成矩阵乘法

所以可以倍增优化

这样是logk*n^3的

 代码:

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define IL inline
#define rint register int
#define me(x) memset(x,0,sizeof(x))
#define fi first
#define se second
#define mid ((h+t)/2)
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
#define setit set<int>::iterator
const int INF=1e9;
char ss[<<],*A=ss,*B=ss;
IL char gc()
{
return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
}
template<class T>void read(T &x)
{
rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=c^;
while (c=gc(),<c&&c<) x=(x<<)+(x<<)+(c^); x*=f;
}
int n,m,s,t,cnt;
struct re{
int d[][];
}ys;
re js(re x,re y)
{
re ans;
rep(i,,)
rep(j,,)
ans.d[i][j]=INF;
rep(k,,cnt)
rep(i,,cnt)
rep(j,,cnt)
ans.d[i][j]=min(ans.d[i][j],x.d[i][k]+y.d[k][j]);
return(ans);
}
re qpow(int x)
{
if (x==) return(ys);
re y=qpow(x/);
y=js(y,y);
if (x%) y=js(y,ys);
return(y);
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
read(n); read(m); read(s); read(t);
rep(i,,)
rep(j,,)
ys.d[i][j]=INF;
map<int,int>M;
rep(i,,m)
{
int x,y,z;
read(x); read(y); read(z);
int x1,x2;
if (!M[y]) x1=M[y]=++cnt; else x1=M[y];
if (!M[z]) x2=M[z]=++cnt; else x2=M[z];
ys.d[x1][x2]=min(ys.d[x1][x2],x);
ys.d[x2][x1]=min(ys.d[x2][x1],x);
}
re ans=qpow(n);
printf("%d",ans.d[M[s]][M[t]]);
return ;
}