BZOJ1706奶牛接力跑

这个东西思路还是不错的。

解法就是把矩阵幂的加法改成取min，乘法改成加法就好，和floyed是一样的。这样的话，矩阵操作一次就相当于松弛了一次最短路。

建矩阵的过程也比较简单，可以离散化，当然下面有另一种更优秀的打法，可以借鉴一下。

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<vector>

#include<set>

#include<map>

#include<queue>

#include<stack>

using namespace std;

int read(){

    int sum=,f=;char x=getchar();

    while(x<''||x>''){

        if(x=='-') f=-;

        x=getchar();

    }while(x>=''&&x<=''){

        sum=sum*+x-'';

        x=getchar();

    }return sum*f;

}

int k,m,s,e,num;

int id[];

struct Matrix{

    int x[][];

    void add(int a,int b,int c){

        x[a][b]=c;

        return ;

    }

    friend Matrix operator * (Matrix a,Matrix b){

        Matrix c;

        memset(c.x,0x3f,sizeof(c.x));

        for(int i=;i<=num;i++)

            for(int j=;j<=num;j++)

                for(int k=;k<=num;k++)

                    c.x[i][j]=min(c.x[i][j],a.x[i][k]+b.x[k][j]);

        return c;

    }

    void db(){

        cout<<endl;

        for(int i=;i<=num;i++){

            for(int j=;j<=num;j++)

                cout<<x[i][j]<<" ";

            cout<<endl;

        }

    }

    void put(int a,int b){

        printf("%d",x[a][b]);

        return ;

    }

}a;

void qpow(int k){

    Matrix c=a,b=a;

//    b.db();

    for(;k;k>>=,b=b*b)

        if(k&) c=c*b;

//    c.db();

    a=c;

}

int main(){

    k=read();m=read();s=read();e=read();

    memset(a.x,0x3f,sizeof(a.x));

    for(int i=,x,y,z;i<=m;i++){

        z=read();x=read();y=read();

        id[x]=id[x]?id[x]:++num;

        id[y]=id[y]?id[y]:++num;

        a.add(id[x],id[y],z);

        a.add(id[y],id[x],z);

    }

//    a.db();

    qpow(k-);

//    a.db();

    a.put(id[s],id[e]);

    return ;

}

这种打法是直接用a做的初始矩阵，根据A=A*A做的操作，因为一开始不太清楚单位矩阵是谁。

后来想通了，以前的单位矩阵之所以是那样的，是因为单位矩阵的定义是另一个矩阵乘完该矩阵还是原矩阵，以前的之所以是对角线全是1，是因为通过矩阵乘后这个矩阵可以满足单位矩阵性质。

那么这个题的单位矩阵是正无穷矩阵，因为该任何一个矩阵乘完该矩阵还是原矩阵（因为取min嘛）。