由传纸条联想到本题
#include <iostream>
#include <cstring>
using namespace std;
const int N=15;
int f[N][N][N][N],w[N][N],n;
int main()
{
cin>>n;
int x,y,z;
while(cin>>x>>y>>z,x||y||z) w[x][y]+=z;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
for(int s=1;s<=n;s++)
if(i!=k||j!=s)
{
int t=w[i][j]+w[k][s];
int &x=f[i][j][k][s];
x=max(x,f[i-1][j][k-1][s]);
x=max(x,f[i][j-1][k-1][s]);
x=max(x,f[i-1][j][k][s-1]);
x=max(x,f[i][j-1][k][s-1]);
x+=t;
}
cout<<f[n][n-1][n-1][n]+w[1][1]+w[n][n]<<endl;//关键点
return 0;
}