题解
三元组矩阵乘法…
数据结构书上一般都会讲到。
因为指定了要求的值的位置，所以可以在矩阵$A\times B$的过程中，只保留$A$的$x$一行上的值，然后用$B$中的值去乘。
对$B\times C$也如此。
这样矩阵乘法的复杂度就会远低于$O(n^3)$，就做完了。
复杂度大概是$O(n^2)$?
实际上这题更麻烦的是读入…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
using namespace std;
typedef long long ll;
int x,y,m,n,o,p;
int Am[6005]={0},Bm[6005]={0};
char input[10005];
int main(){
int i,j,u,v,val;
scanf("%d%d%d%d%d%d",&x,&y,&m,&n,&o,&p);
fgets(input,10000,stdin);
for(;;){
fgets(input,10000,stdin);
if(!isdigit(input[0]))break;
sscanf(input,"%d%d%d",&u,&v,&val);
if(u==x)Am[v]=val;
}
for(;;){
fgets(input,10000,stdin);
if(!isdigit(input[0]))break;
sscanf(input,"%d%d%d",&u,&v,&val);
Bm[v]+=Am[u]*val;
}
memcpy(Am,Bm,sizeof(Bm));
memset(Bm,0,sizeof(Bm));
while(~scanf("%d%d%d",&u,&v,&val))
Bm[v]+=Am[u]*val;
printf("%d\n",Bm[y]);
return 0;
}