Question description

The world is in love, only I love learning. ——Foreword.
2333, a single dog, but who unexpectedly likes dog food, Yuki firmly believes: “Since ancient times, red and blue out of the CP, black and white is the best red and green match, natural golden purple double -pair, life and death follow red and yellow, life and death follow the red and yellow. Bai Ziyi meets the spring full of spring, thousands of miles are white and green, and red and black came together. “The CP pairing principle was being in vain. point. It can be seen that the dead house is really a promising career. At the end of this season, a group of CPs are holding a football game. They want to be lazy and lovely Dead House Yamana Kenka but hear the more lovely cheering sound of Li Yuan Chiyo. He feels helpless. The place is lazy, and does not want to significantly affect the image in the heart of the girl too much. The playground is a N*N square matrix. There is a non -negative combination on each grid. A (i, J) means how much a point will be reduced here. (i, j) = 1 indicates that the grid (i, j) is selected, and B (i, J) = 0 means that the grid (i, j) is not selected. Matrix B must meet three conditions, Shan Gelongfu will not be ended by the red card.
B(1,2)+B(1,3)+...B(1,n)=1
B(1,n)+B(2,n)+...B(n−1,n)=1
ΣB(k,i)(1<=k<=n)=ΣB(i,j)(1<=j<=n)(1<i<n)
As a dead house, you must also have the same ideal about girls like the super cute house. Then please help him and find out a plan that makes him minimize the minimum.

input

The first line of an integer n means the size of the playground, the grid of n line n column. The next n line n integers represent A (i, j).

output

A line of integer indicates how much scores have been reduced in the lovely Kurihara Chiyo’s heart.

Sample input

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

Sample output

1
For the first 10%data: n <= 10
For the first 20%data: n <= 100
For the first 50%data: n <= 1000
For 100%data: n <= 2000

At first look at the question, you will feel that this question is difficult, and then think about a variety of mathematical methods, or some weird messy methods.
Actually, if you look closely at this question, it is actually a map of the discussion (amazing ing
A

B
B(1,2)+B(1,3)+...B(1,n)=1 1

1
B(1,n)+B(2,n)+...B(n−1,n)=1 n

n
ΣB(k,i)=ΣB(i,j) 2

n−1
1−>n 1

n
SPFA
still is still the code without annotation, sorry ~

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 2005
#define ll long long
int n,vis[N];
ll A[N][N],dis[N],ans,rnd=1ll<<60;
queue<int>q;
ll getll()
{
    ll p=0;char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9')
        p=p*10+c-'0',c=getchar();
    return p;
}
void putll(ll a)
{
    if(a<0)putchar('-'),a=-a;
    if(a>9)putll(a/10);
    putchar(a%10+'0');
}
void SPFA(int s)
{
    for(int i=0;i<=n;i++)
        dis[i]=1ll<<60;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=1;i<=n;i++)
        {
            if(dis[x]+A[x][i]<dis[i])
            {
                dis[i]=dis[x]+A[x][i];
                if(!vis[i])
                {
                    vis[i]=1;
                    q.push(i);
                }
            }
        }
        vis[x]=0;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            A[i][j]=getll();
    SPFA(1);
    ans=dis[n];
    for(int i=2;i<=n;i++)
        rnd=min(rnd,dis[i]+A[i][1]);
    SPFA(n);
    for(int i=1;i<n;i++)
        ans=min(ans,rnd+dis[i]+A[i][n]);
    putll(ans);
    putchar(10);
}