找不出哪里错了,来个佬看看,求
查看原帖
找不出哪里错了,来个佬看看,求
256996
かわいい子楼主2023/10/5 22:18

实在不知道哪里错了
求看看

//#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*/
2023/10/5 22:18
加载中...