P2886 [USACO07NOV]Cow Relays G

2021年09月15日 阅读数:1
这篇文章主要向大家介绍P2886 [USACO07NOV]Cow Relays G,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

原题连接ios

考察:矩阵快速幂+floyd最短路ide

思路:spa

        首先明白这道题不是矩阵相乘,res[i][j] = min(res[i][j],a[i][k]+b[k][j]). a[i][j]若是表明通过x条路的最短路,b[i][j]表明通过y条路的最短路.那么res是通过x+y条路的最短路.get

注意:string

        图上的点须要通过离散化,自环的路径不须要为0.由于n至少为1.it

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 using namespace std;
 6 const int N = 1010,M = 110,INF=  0x3f3f3f3f;
 7 int n,t,s,e,idx;
 8 int g[M][M],mp[M][M],h[N];
 9 void mul(int f[][M],int a[][M])
10 {
11     int res[M][M];
12     memset(res,INF,sizeof res);
13     for(int k=1;k<=idx;k++)
14       for(int i=1;i<=idx;i++)
15         for(int j=1;j<=idx;j++)
16           res[i][j] = min(res[i][j],f[i][k]+a[k][j]);
17     memcpy(f,res,sizeof res);
18 }
19 int main()
20 {
21     scanf("%d%d%d%d",&n,&t,&s,&e);
22     memset(g,INF,sizeof g);
23     while(t--) 
24     {
25         int u,v,w; scanf("%d%d%d",&w,&u,&v);
26         if(!h[u]) h[u] = ++idx;
27         if(!h[v]) h[v] = ++idx;
28         g[h[u]][h[v]] = min(g[h[u]][h[v]],w);
29         g[h[v]][h[u]] = g[h[u]][h[v]];
30     }
31     memcpy(mp,g,sizeof g);
32     n--;
33     while(n)
34     {
35         if(n&1) mul(g,mp);
36         mul(mp,mp);
37         n>>=1;
38     }
39     printf("%d\n",g[h[s]][h[e]]);
40     return 0;
41 }