P2886 [USACO07NOV]牛继电器Cow Relays[dp,矩阵乘法]

题目描述

For their physical fitness program, N ($2 ≤ N ≤ 1000000$) cows have decided to run a relay race using the T ( $2 ≤ T ≤ 100$ ) cow trails throughout the pasture.

Each trail connects two different intersections ($1 ≤ I1_i ≤ 1000$; $1 ≤ I2_i ≤1000$ ), each of which is the termination for at least two trails. The cows know the lengthi of each trail ($1 ≤ length_i ≤ 1000$), the two intersections the trail connects, and they know that no two intersections are directly connected by two different trails. The trails form a structure known mathematically as a graph.

To run the relay, the N cows position themselves at various intersections (some intersections might have more than one cow). They must position themselves properly so that they can hand off the baton cow-by-cow and end up at the proper finishing place.

Write a program to help position the cows. Find the shortest path that connects the starting intersection (S) and the ending intersection (E) and traverses exactly N cow trails.

给出一张无向连通图,求 $S$ 到 $E$ 经过 $k$ 条边的最短路。

输入输出格式

输入格式:

  • Line 1: Four space-separated integers: $N, T, S, and E$
  • Lines 2.. $T+1$ : Line $i+1$ describes trail i with three space-separated integers: $length_i$ , $I1_i$ , and $I2i$

输出格式:

  • Line 1: A single integer that is the shortest distance from intersection S to intersection E that traverses exactly N cow trails.

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

输出样例#1:

1
10

题解

$f_{k,i,j}$表示$i->j$ 走 $k$ 条路的最小值。

然后用矩阵乘法转移,第一维省掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
void qmax(long long &x,long long y) {if (x<y) x=y;}
void qmin(long long &x,long long y) {if (x>y) x=y;}
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
int n,t,S,E,Z,X,Y;
long long INF;
int Map[10010],ID;
long long f[120][120],s[120][120],a[120][120],b[120][120],c[120][120];
void cheng(int x)
{
if (x==0) {memcpy(a,s,sizeof(s));memcpy(b,f,sizeof(f));} else {memcpy(a,f,sizeof(f));memcpy(b,f,sizeof(f));}
for (int i=1;i<=ID;i++) for (int j=1;j<=ID;j++) c[i][j]=233333333333333;
for (int i=1;i<=ID;i++)
for (int j=1;j<=ID;j++)
{
for (int k=1;k<=ID;k++) qmin(c[i][j],a[i][k]+b[k][j]);
}
if (x==0) memcpy(s,c,sizeof(c)); else memcpy(f,c,sizeof(c));
}
int main()
{
n=read();t=read();S=read();E=read();
for (int i=1;i<=119;i++) for (int j=1;j<=119;j++) f[i][j]=23333333333333333;
for (int i=1;i<=t;i++)
{
Z=read();X=read();Y=read();
if (Map[X]==0) Map[X]=++ID;X=Map[X];//离散化
if (Map[Y]==0) Map[Y]=++ID;Y=Map[Y];
if ((long long)Z<f[X][Y]) f[X][Y]=f[Y][X]=Z;
}
memcpy(s,f,sizeof(f));
n--;
while (n)//矩乘
{
if (n&1) cheng(0);
cheng(1);
n>>=1;
}
printf("%lld\n",s[Map[S]][Map[E]]);
return 0;
}