问题: relays 奶牛接力跑

时间限制: 1 Sec  内存限制: 256 MB

题面

---

题目描述

FJ的N(2 <= N <= 1,000,000)头奶牛选择了接力跑作为她们的日常锻炼项目。至于进行接力跑的地点 自然是在牧场中现有的T(2 <= T <= 100)条跑道上。 农场上的跑道有一些交汇点，每条跑道都连结了两个不同的交汇点 I1_i和I2_i(1 <= I1_i <= 1,000; 1 <= I2_i <= 1,000)。每个交汇点都是至少两条跑道的端点。 奶牛们知道每条跑道的长度length_i(1 <= length_i <= 1,000)，以及每条跑道连结的交汇点的编号 并且，没有哪两个交汇点由两条不同的跑道直接相连。你可以认为这些交汇点和跑道构成了一张图。 为了完成一场接力跑，所有N头奶牛在跑步开始之前都要站在某个交汇点上（有些交汇点上可能站着不只1头奶牛）。当然，她们的站位要保证她们能够将接力棒顺次传递，并且最后持棒的奶牛要停在预设的终点。 你的任务是，写一个程序，计算在接力跑的起点(S)和终点(E)确定的情况下，奶牛们跑步路径可能的最小总长度。显然，这条路径必须恰好经过N条跑道。

输入格式

第1行: 4个用空格隔开的整数：N，T，S，以及E

第2..T+1行: 第i+1为3个以空格隔开的整数：length_i，I1_i，以及I2_i， 描述了第i条跑道。

输出格式

第1行: 输出1个正整数，表示起点为S、终点为E，并且恰好经过N条跑道的路 径的最小长度

样例输入

2 6 6 4

11 4 6

4 4 8

8 4 9

6 6 8

2 6 9

3 8 9

 

样例输出

10

题解

---

这道题是拓展矩阵乘法的入门题，也可以说是倍增Floyed。（同时也是我的第一道线性代数提高题）

本文主要从矩阵乘法角度入手。（因为说是倍增Floyed有点牵强，倍增主要体现在矩阵快速幂上）

我们都知道，使用矩阵快速幂的目的在于降低运算次数，以达到降低时间复杂度的效果。

矩阵乘法的运算代码如下：

Mal Mal_MULTI(Mal a,Mal b){    Mal ans;    for(int i=1;i<=cnt;++i)        for(int j=1;j<=cnt;++j)            for(int k=1;k<=cnt;++k)                ans.data[i][j]=a.data[i][k]*b.data[k][j]    return ans;}

十分基础的矩阵乘法。

然而本题和它不同。本题要求的是求路径长度。所以显然不是各项相乘，而应该是相加。

但是相加显然不能满足题意要求的：最小路径。

所以我们需要取min。

于是矩阵乘法的函数就变成了这个样子：

Mal Mal_MULTI(Mal a,Mal b){    Mal ans;    memset(ans.data,0x3f,sizeof(ans.data));    for(rint i=1;i<=cnt;++i)        for(rint j=1;j<=cnt;++j)            for(rint k=1;k<=cnt;++k)                ans.data[i][j]=min(ans.data[i][j],a.data[i][k]+b.data[k][j]);    return ans;}

相信大家都看出来了，这显然与floyed十分相似。所以我们也称他倍增优化的Floyed算法。

然而这样求不是个事啊QAQ，N大的吓人，1e6，所以我们又搬出了矩阵快速幂。

别忘了开离散化哦～

代码如下：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define rint register intusing namespace std;int in_n,in_t,in_s,in_e,ls_dy[1000006],in_x,in_y;int cnt,in_l;struct Mal{ int data[103][103],line;}map,anss;Mal Mal_MULTI(Mal a,Mal b){ Mal ans; memset(ans.data,0x3f,sizeof(ans.data)); for(rint i=1;i<=cnt;++i) for(rint j=1;j<=cnt;++j) for(rint k=1;k<=cnt;++k) ans.data[i][j]=min(ans.data[i][j],a.data[i][k]+b.data[k][j]); return ans;}Mal Mal_QPOW(Mal a,int x){ Mal ans; memset(ans.data,0x3f,sizeof(ans.data)); for(rint i=1;i<=cnt;++i) ans.data[i][i]=0; while(x) { if(x&1)ans=Mal_MULTI(ans,a); a=Mal_MULTI(a,a);x>>=1; } return ans;}int main(){ memset(anss.data,0x3f,sizeof(anss.data)); memset(map.data,0x3f,sizeof(map.data));// cout<
            
             <