实在不知道哪里错了
求看看
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <random>
#include <stack>
#include <list>
#include <algorithm>
#define ri register int // inline int 0x7f:max ,0xaf:min
using namespace std;
#define ll long long
//typedef long long ll
const int numm = 1e6+5;
int n , q ;
ll dis[105][105],dit[105][105];
ll red[105][105];
inline int max (int x,int y){return x>y?x:y;}
inline int min (int x,int y){return x>y?y:x;}
bool flyod(int t) {
int res = t /n ; int mo = t % n ;
ll ans = 0 ;
for(int i = 1 ; i <= n ; i ++ ){
for(int j = i ; j <= n ; j ++ ) {
dit[i][j] = max(red[i][j],dis[i][j] - res) ;
dit[j][i] = dit[i][j] ;
// cout << red[i][j] <<" " << dis[i][j] - res << endl ;
if(i <= mo) {dit[i][j] = max(red[i][j],dit[i][j] - 1) ; dit[j][i] = dit[i][j];}
// cout <<"i:"<<i<<" j:" << j <<" ::"<< dit[i][j] << endl ;
// cout << dit[i][j] << " " ;
}
// cout<<endl;
}
// cout<<endl;
// for(int i = 1 ; i <= n ; i ++ ){
// for(int j = 1 ; j <= n ; j ++ ) {
// cout << dit[i][j]<<" ";
// // ans += dit[i][j] ;
// }
// cout<<endl;
// }
// cout<<endl;
// for(int i = 1 ; i <= n ; i ++ ) dit[i][i] = 0 ;
for(int k = 1 ; k <= n ; k ++ )
for(int i = 1 ; i <= n ; i ++ )
for(int j = 1 ; j <= n ; j ++ )
dit[i][j] = min(dit[i][j],dit[i][k]+dit[k][j]) ;
for(int i = 1 ; i <= n ; i ++ ){
for(int j = 1 ; j <= n ; j ++ ) {
// cout << dit[i][j]<<" ";
ans += dit[i][j] ;
}
// cout<<endl;
}
// cout << "ans:" << ans << endl ;
if(ans <= q) return true ;
return false ;
}
void solve() {
cin >> n >> q ;
for(int i = 1 ; i <= n ; i ++ )
for(int j = 1 ; j <= n ; j ++ )
cin >> dis[i][j] ;
for(int i = 1 ; i <= n ; i ++ )
for(int j = 1 ; j <= n ; j ++ ) cin >> red[i][j] ;
int l = 0 , r = 1e9+5 ;
while(l < r) {
int mid = l + r >> 1 ;
if(flyod(mid)) {r = mid ; //cout << "r:" << r << endl ;
}
else l = mid + 1 ;
}
// flyod(31);
if(flyod(l)) cout << l ;
else cout << -1 ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve() ;
system("pause");
return 0;
}
/*10 200
0 5 6 2 9 7 7 9 7 9
5 0 6 7 2 3 1 5 0 9
6 6 0 8 8 8 9 6 8 8
2 7 8 0 8 9 6 6 3 9
9 2 8 8 0 3 4 5 7 7
7 3 8 9 3 0 8 7 3 8
7 1 9 6 4 8 0 8 3 6
9 5 6 6 5 7 8 0 8 7
7 0 8 3 7 3 3 8 0 9
9 9 8 9 7 8 6 7 9 0
0 4 0 0 4 6 4 4 6 1
4 0 2 0 2 2 1 2 0 6
0 2 0 7 7 1 6 5 4 3
0 0 7 0 8 9 5 3 1 9
4 2 7 8 0 2 4 4 2 6
6 2 1 9 2 0 8 7 3 5
4 1 6 5 4 8 0 2 2 5
4 2 5 3 4 7 2 0 2 6
6 0 4 1 2 3 2 2 0 9
1 6 3 9 6 5 5 6 9 0*/