离散化+倍增优化Floyed

#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=205;const int MAXM=1005;int n,T,S,E,cnt,mx,mi=MAXM;int st[MAXM],s[MAXM];int x[MAXN],y[MAXN],ln[MAXN];struct Matrix{    int v[MAXN][MAXN];    int x,y;        void clear(){memset(v,0,sizeof(v));x=y=0;return;}    void Mmul(Matrix a,Matrix b)    {        memset(v,0x3f,sizeof(v));        x=a.x,y=b.y;        int c=a.y;        for(int k=1;k<=c;++k){            for(int i=1;i<=x;++i){                for(int j=1;j<=y;++j){                    v[i][j]=min(v[i][j],a.v[i][k]+b.v[k][j]);                }            }        }return;    }        Matrix Mpw(Matrix a,int b)    {        Matrix x=a;        while(b){            if(b&1) x.Mmul(x,a);            b>>=1;a.Mmul(a,a);        }return x;    }        void write()    {        for(int i=1;i<=x;++i){            for(int j=1;j<=y;++j){                printf("%d ",v[i][j]);            }puts("");        }puts("");        return;    }}F;int main(){    scanf("%d%d%d%d",&n,&T,&S,&E);    for(int i=1;i<=T;++i){        scanf("%d%d%d",&ln[i],&x[i],&y[i]);        st[x[i]]=st[y[i]]=1;        mi=min(mi,min(x[i],y[i]));        mx=max(mx,max(x[i],y[i]));    }for(int i=mi;i<=mx;++i) if(st[i]) s[i]=++s[0];    S=s[S],E=s[E];    memset(F.v,0x3f,sizeof(F.v));    F.x=F.y=s[0];    for(int i=1;i<=T;++i) F.v[s[x[i]]][s[y[i]]]=F.v[s[y[i]]][s[x[i]]]=ln[i];    F=F.Mpw(F,n-1);    printf("%d\n",F.v[S][E]);    return 0;}