#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define int long long int
#define endl '\n'
#define N 2050
#define M 15
#define big 2147483647
#define bigg 9223372036854775807
#define pb push_back
#define p push
#define ins insert
#define f first
#define s second
int dp[N][N],arr[N][N];
int nnn;
vector<pair<int,int>> hesap(int l,int r){
vector<pair<int,int>> cev;
//cout<<l<<" "<<r<<endl;
if(r<l)return cev;
if(l==r){
dp[l][r]=dp[r][l]=0;
cev.pb({l,r});
cev.pb({r,l});
return cev;
}
int mid=(l+r)/2;
vector<pair<int,int>> a=hesap(l,mid), b=hesap(mid+1,r);
int mn=bigg;
for(auto u:a){
int x=u.f, y=u.s;
for(auto v:b){
int m=v.f,n=v.s;
int top=dp[x][y]+dp[m][n];
int yes=arr[y][m], ok=arr[x][n];
if(dp[x][n]==-1){
dp[x][n]=top+yes;
cev.pb({x,n});
cev.pb({n,x});
}
dp[x][n]=min(dp[x][n],top+yes);
dp[n][x]=dp[x][n];
if(dp[y][m]==-1){
dp[y][m]=top+ok;
cev.pb({y,m});
cev.pb({m,y});
}
dp[y][m]=min(dp[y][m],top+yes);
dp[m][y]=dp[y][m];
//cout<<x<<" "<<y<<" "<<m<<" "<<n<<": "<<dp[x][n]<<" "<<dp[m][y]<<" _ "<<ok<<" "<<yes<<" "<<top<<endl;
mn=min(mn,min(dp[x][n],dp[m][y]));
}
}
if(l==1&&r==nnn){
cout<<mn<<" "<<endl;
}
return cev;
}
signed main(){
lalala;
memset(dp,-1,sizeof(dp));
cin>>nnn;
for(int i=1;i<=nnn;i++){
for(int j=1;j<=nnn;j++)cin>>arr[i][j];
}
hesap(1,nnn);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
37212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
37212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
37212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
37212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
