给定无向连通图，求经过k条边，s到t的最短路

 

Floyd形式的矩阵乘法，同样满足结合律，所以可以进行快速幂。

 

离散化大可不必sort+unique，因为我们甚至并不在乎相对大小，只是要一个唯一编号，可以开一个桶记录

 

之所以进行k-1次快速幂，是因为邻接矩阵本身就走了一步了。

 

#include
     
      #include
      
       #include
       
        using namespace std;const int MAXN=256;int k,m,s,t;int a[MAXN][MAXN];int id[MAXN<<5],tot;struct Mat{  int data[MAXN][MAXN];  Mat(int x=0){memset(data,x,sizeof(data));}  Mat operator*(const Mat &rhs){    Mat ret(0x3f);    for(int k=1;k<=tot;k++)      for(int i=1;i<=tot;i++)        for(int j=1;j<=tot;j++)          ret.data[i][j]=min(ret.data[i][j],data[i][k]+rhs.data[k][j]);    return ret;  }  Mat operator^(int x){    Mat ret;memcpy(ret.data,a,sizeof(a));    for(Mat base=*this;x;x>>=1){      if(x&1) ret=ret*base;      base=base*base;    }    return ret;  }};int main(){  memset(a,0x3f,sizeof(a));//  cin>>k>>m>>s>>t;  for(int i=1;i<=m;i++){    int x,y,w;    cin>>w>>x>>y;    if(!id[x])id[x]=++tot;    if(!id[y])id[y]=++tot;    x=id[x];y=id[y];    a[x][y]=a[y][x]=w;  }  s=id[s];t=id[t];  Mat e;  memcpy(e.data,a,sizeof(a));  e=e^(k-1);  cout<