poj 3613(最短路)-白红宇

poj 3613(最短路)

阅读量：5144 次

发布时间：2019-06-13

本文共 1255 字，大约阅读时间需要 4 分钟。

题意：求解经过不多于某边数的最短路

思路：矩阵连乘，乘的次数就是不多于某边数的最短路，题目给出的顶点需要映射处理

View Code

1 #include
      
        2 #include
        3 #include
        
          4 #include
         
           5 using namespace std; 6 #define N 202 7 struct matrix{ 8     int f[N][N]; 9     matrix(){10         memset(f,0x3f,sizeof(f));11     }12 };13 int num;14 matrix mul(matrix a,matrix b)15 {16     matrix c;17     for(int i=1;i<=num;i++)18     for(int j=1;j<=num;j++)19     for(int k=1;k<=num;k++)20     {21         c.f[i][j]=min(c.f[i][j],a.f[i][k]+b.f[k][j]);22     }23     return c;24 }25 matrix pow(matrix m,int n)26 {27     if(n==1)return m;28     matrix tmp=pow(m,n/2);29     if(n&1)return mul(mul(tmp,tmp),m);30     return mul(tmp,tmp);31 }32 map
          
            mp;33 int main()34 {35     int n,t,s,e;36     num=0;37     scanf("%d%d%d%d",&n,&t,&s,&e);38     mp.clear();39     matrix c;40     for(int i=1;i<=t;i++)41     {42         int a,b,w;43         scanf("%d%d%d",&w,&a,&b);44         if(mp[a]==0)mp[a]=++num;45         if(mp[b]==0)mp[b]=++num;46         c.f[mp[a]][mp[b]]=c.f[mp[b]][mp[a]]=w;47     }48     pow(c,1);49     matrix out=pow(c,n);50     cout<
           
            <