priority_queue returns maximum value at each point. But in Dijkstra we want to pick up the smallest possible distance every time. So, when we push the negative distance value into the priority_queue, the maximum value becomes the smallest one. Therefore, each time we can get minimum distance in top of the priority_queue.

Actually it's a formal binary search approach. If ok function returns false for any mid value that means for taking "mid" maximum gap we can't put C cows. As we know number of cows we can put is inversely proportional to the gap, we have to reduce the maximum gap to put C cows. So we can eliminate mid to upper bound range of the binary search.

I've updated my code and I think this updated code will give you more intuition. I've replaced the return statement of "ok" function

return (cows < given_cows)

with

return (cows >= given_cows)

Now if "ok" function returns true value then, for the current mid value we can put more than or equal number of cows than given number of cows. As current mid can be the answer, we store mid as answer and increase the lower bound to mid+1. Why? Because we're trying to find the largest X for which (cows >= given_cows) condition is true. If "ok" returns false value, upper bound needs to be updated to mid-1. But why adding 1 with answer? I'm sorry to say that I can't explain it. I did it because of sample example.

For input:

1

Hints:

Solution:

#include <bits/stdc++.h>
using namespace std;
#define mxn  5010
 
char str[mxn] , rev[mxn];

#include <bits/stdc++.h>
using namespace std;
 
#define mxn  100010
 
struct edge{
    int u, v, a, b;
};
 
edge edg[mxn];
int rep[mxn];
int n, m, mstA = 0, mstB = 0;
 
 
void setRep(){
    for(int i=0; i<mxn; i++) rep[i] = i;
}
 
int findRep(int n){
    if(rep[n]!=n) rep[n] = findRep(rep[n]);
    return rep[n];
}
 
bool connected(int x, int y){

Hints:

Solution:

#include <bits/stdc++.h>
using namespace std;
#define pb            push_back
#define mp            make_pair
#define ff            first

#include <bits/stdc++.h>
using namespace std;
#define sfi(x)        scanf("%d", &x)
#define pb            push_back
#define mp            make_pair
#define INF           1000000000
#define mxn           155
 
int cost[mxn][mxn];
int ranking[mxn];
int qsource[6010] , qdest[6010] , ans[6010];
vector< int > query[mxn];
 
int main()
{
    int tc, n, c, r, s, d, p, q;
    sfi(tc);
 
    for(int t=1; t<=tc; t++){
        sfi(n);
        for(int i=1; i<=n; i++){
            cost[i][i] = 0;
            for(int j=i+1; j<=n; j++){
                sfi(c);

Hints:

Solution:

#include <bits/stdc++.h>
using namespace std;
 
#define sf(x)         scanf("%d", &x)
#define pf(x)         printf("%d\n", x)
 
int main()
{
    int n,t;
    sf(t);
 

Hints:

Could you explain how it works for a pair i , j (i>j)?