D64 最短路 Floyd算法+矩阵快速幂

// 最短路 Floyd算法+矩阵快速幂 O(m^3*logn)=200^3*20
#include<bits/stdc++.h>
using namespace std;

const int N=210;
int n,T,S,E,m;
int t[N][N],d[N][N],res[N][N];

void Floyd(int c[][N],int a[][N],int b[][N]){
  memset(t,0x3f,sizeof t); //初始化临时数组
  for(int k=1; k<=m; k++)
    for(int i=1; i<=m; i++)
      for(int j=1; j<=m; j++)
        t[i][j]=min(t[i][j],a[i][k]+b[k][j]); //数组t=数组a+数组b
  memcpy(c,t,sizeof t); //复制t到c
}
void qsm(){
  memset(res,0x3f,sizeof res);
  for(int i=1;i<=m;i++) res[i][i]=0; //初始化为对角为0的单位矩阵
  while(n){
    if(n&1) Floyd(res,res,d); //res=res+d 累加答案
    Floyd(d,d,d); //d=d+d 即经过2,4,8...条边的最短路
    n>>=1;
  }
}
int main(){
  cin>>n>>T>>S>>E; //n条边,T条边,起点,终点
  memset(d,0x3f,sizeof d); //注意d[i][i]不能初始化为0，因自己走向自己不合法
  map<int,int> mp;
  if(!mp.count(S)) S=(mp[S]=++m); //点的离散化，把大整数映射为小整数
  if(!mp.count(E)) E=(mp[E]=++m);
  for(int a,b,c;T--;){
    cin>>c>>a>>b;
    if(!mp.count(a)) mp[a]=++m;
    if(!mp.count(b)) mp[b]=++m; //最多边数T=100,点数m=200
    a=mp[a]; b=mp[b];
    d[a][b]=d[b][a]=min(d[a][b],c); //初始时d为仅经过一条边的最短路
  }
  
  qsm(); //矩阵快速幂
  cout<<res[S][E];
}

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int a[210][210];
    node(){memset(a, 63, sizeof a);}
};
int D[1100], n;

node operator*(node A, node B)
{
    node C;
    for (int k=1; k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j =1;j<=n;j++)
                C.a[i][j]=min(C.a[i][j],A.a[i][k]+B.a[k][j]);
    return C;
}
node qpow(node A, int b)
{
    node C;for(int i=1;i<=n;i++)C.a[i][i]=0;//注意单位矩阵为0
    for(;b;b>>=1)
    {
        if(b&1)C=C*A; 
        A=A*A;
    }
    return C;
}
int main()
{
    int N, T, st, ed;scanf ("%d%d%d%d", &N, &T, &st, &ed);
    memset(D,0,sizeof D);n=0;
    node f;
    for (int i=1;i<=T;i++)
    {
        int x, y, w;scanf("%d%d%d", &w, &x, &y);
        if(!D[x]) D[x]=++n;
        if(!D[y]) D[y]=++n;
        f.a[D[x]][D[y]]=f.a[D[y]][D[x]]=w;
    }
    f=qpow(f, N);
    printf ("%d\n", f.a[D[st]][D[ed]]);
    return 0;
}