BZOJ 1706: [usaco2007 Nov]relays 奶牛接力跑 倍增Floyd

#include <bits/stdc++.h>   
#define N 300 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;   
map<int,int>pp;  
int n,m,S,T,tot,dis[N][N][30],tmp[N][N],g[N][N];   
int main() 
{  
    int i,j,k,l; 
    // setIO("input");  
    scanf("%d%d%d%d",&n,&m,&S,&T);                   
    memset(dis,0x3f,sizeof(dis));   
    for(i=1;i<=m;++i) 
    {    
        int a,b,c; 
        scanf("%d%d%d",&c,&b,&a);   
        if(!pp[a]) pp[a]=++tot;  
        if(!pp[b]) pp[b]=++tot;  
        a=pp[a],b=pp[b];  
        dis[a][b][0]=dis[b][a][0]=min(dis[a][b][0],c);         
    } 
    if(!pp[S]) pp[S]=++tot; 
    if(!pp[T]) pp[T]=++tot;
    S=pp[S],T=pp[T];       
    for(l=1;l<=20;++l) 
    { 
        for(k=1;k<=tot;++k) 
            for(i=1;i<=tot;++i) 
                for(j=1;j<=tot;++j) 
                    dis[i][j][l]=min(dis[i][j][l], dis[i][k][l-1]+dis[k][j][l-1]);       
    }        
    memset(tmp,0x3f,sizeof(tmp));     
    int flag=0; 
    for(l=0;(1<<l)<=n;++l) 
    {
        if(n&(1<<l))      // 2^l    
        {  
            if(flag==0) 
            {
                flag=1;   
                for(i=1;i<=tot;++i) 
                    for(j=1;j<=tot;++j) tmp[i][j]=dis[i][j][l];   
            }    
            else 
            {
                memset(g,0x3f,sizeof(g));    
                for(k=1;k<=tot;++k)  
                { 
                    for(i=1;i<=tot;++i) 
                    { 
                        for(j=1;j<=tot;++j) 
                        {
                            g[i][j]=min(g[i][j], tmp[i][k]+dis[k][j][l]);                           
                        }   
                    }
                }   
                for(i=1;i<=tot;++i) 
                    for(j=1;j<=tot;++j) tmp[i][j]=g[i][j];    
            }
        }
    }
    printf("%d\n",tmp[S][T]);   
    return 0; 
}