123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to find the city with
the smallest number of neighbors. */
int findCity(int n, int m, vector<vector<int>>& edges,
int distanceThreshold) {
// Adjacency matrix to store the graph
vector<vector<int>> adjMat(n, vector<int>(n, 1e9));
// Filling up the adjacency matrix
for(auto it : edges) {
adjMat[it[0]][it[1]] = it[2];
adjMat[it[1]][it[0]] = it[2];
}
// Applying Floyd Warshall Algorithm
// For intermediate node k
for(int k=0; k<n; k++) {
// node i ---> node j
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
adjMat[i][j] =
min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]);
}
}
}
// To store the minimum count of neighbors
int minCount = 1e9;
/* To store the answer (city having
smallest number of neighbors) */
int ans;
// Check every city
for(int i=0; i<n; i++) {
/* To count the neighbors of given city
having distance lesser than threshold */
int count = 0;
// City i ---> City j
for(int j=0; j<n; j++) {
/* If the distance to reach city j from
city i is less than threshold */
if(i != j && adjMat[i][j] <= distanceThreshold) {
// Increment count
count++;
}
}
// if current count is less than minimum count
if(count < minCount) {
// Update minimum count
minCount = count;
// Store the answer
ans = i;
}
/* Else if current count is
equal to minimum count */
else if(count == minCount) {
/* Update the answer (to store
city with greater number) */
ans = i;
}
}
// Return the resulting city as answer
return ans;
}
};
int main() {
int N=4, M=4;
vector<vector<int>> edges ={
{0,1,3},{1,2,1},
{1,3,4},{2,3,1}
};
int distanceThreshold = 4;
/* Creating an instance of
Solution class */
Solution sol;
/* Function to find the city with
the smallest number of neighbors. */
int ans = sol.findCity(N, M, edges, distanceThreshold);
// Output
cout << "The city with smallest number of neighbors (with given threshold) is: " << ans;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104
import java.util.*;
class Solution {
/* Function to find the city with
the smallest number of neighbors. */
public int findCity(int n, int m, int[][] edges,
int distanceThreshold) {
// Adjacency matrix to store the graph
int[][] adjMat = new int[n][n];
for (int[] row : adjMat) Arrays.fill(row, (int)1e9);
// Filling up the adjacency matrix
for(int[] it : edges) {
adjMat[it[0]][it[1]] = it[2];
adjMat[it[1]][it[0]] = it[2];
}
// Applying Floyd Warshall Algorithm
// For intermediate node k
for(int k = 0; k < n; k++) {
// node i ---> node j
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
adjMat[i][j] =
Math.min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]);
}
}
}
// To store the minimum count of neighbors
int minCount = (int)1e9;
/* To store the answer (city having
smallest number of neighbors) */
int ans = -1;
// Check every city
for(int i = 0; i < n; i++) {
/* To count the neighbors of given city
having distance lesser than threshold */
int count = 0;
// City i ---> City j
for(int j = 0; j < n; j++) {
/* If the distance to reach city j from
city i is less than threshold */
if(i != j && adjMat[i][j] <= distanceThreshold) {
// Increment count
count++;
}
}
// if current count is less than minimum count
if(count < minCount) {
// Update minimum count
minCount = count;
// Store the answer
ans = i;
}
/* Else if current count is
equal to minimum count */
else if(count == minCount) {
/* Update the answer (to store
city with greater number) */
ans = i;
}
}
// Return the resulting city as answer
return ans;
}
public static void main(String[] args) {
int N = 4, M = 4;
int[][] edges = {
{0, 1, 3}, {1, 2, 1},
{1, 3, 4}, {2, 3, 1}
};
int distanceThreshold = 4;
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function to find the city with
the smallest number of neighbors. */
int ans = sol.findCity(N, M, edges, distanceThreshold);
// Output
System.out.println("The city with smallest number of neighbors (with given threshold) is: " + ans);
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
class Solution:
# Function to find the city with
# the smallest number of neighbors.
def findCity(self, n, m, edges, distanceThreshold):
# Adjacency matrix to store the graph
adjMat = [[1e9] * n for _ in range(n)]
# Filling up the adjacency matrix
for it in edges:
adjMat[it[0]][it[1]] = it[2]
adjMat[it[1]][it[0]] = it[2]
# Applying Floyd Warshall Algorithm
# For intermediate node k
for k in range(n):
# node i ---> node j
for i in range(n):
for j in range(n):
adjMat[i][j] = min(adjMat[i][j], adjMat[i][k] + adjMat[k][j])
# To store the minimum count of neighbors
minCount = int(1e9)
# To store the answer (city having
# smallest number of neighbors)
ans = -1
# Check every city
for i in range(n):
# To count the neighbors of given city
# having distance lesser than threshold
count = 0
# City i ---> City j
for j in range(n):
# If the distance to reach city j from
# city i is less than threshold
if i != j and adjMat[i][j] <= distanceThreshold:
# Increment count
count += 1
# if current count is less than minimum count
if count < minCount:
# Update minimum count
minCount = count
# Store the answer
ans = i
# Else if current count is
# equal to minimum count
elif count == minCount:
# Update the answer (to store
# city with greater number)
ans = i
# Return the resulting city as answer
return ans
# Main function to test the solution
if __name__ == "__main__":
N, M = 4, 4
edges = [
[0, 1, 3], [1, 2, 1],
[1, 3, 4], [2, 3, 1]
]
distanceThreshold = 4
# Creating an instance of
# Solution class
sol = Solution()
# Function to find the city with
# the smallest number of neighbors.
ans = sol.findCity(N, M, edges, distanceThreshold)
# Output
print("The city with smallest number of neighbors (with given threshold) is:", ans)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104
class Solution {
/* Function to find the city with
the smallest number of neighbors. */
findCity(n, m, edges, distanceThreshold) {
// Adjacency matrix to store the graph
let adjMat = Array.from({ length: n }, () => Array(n).fill(1e9));
// Filling up the adjacency matrix
for (let it of edges) {
adjMat[it[0]][it[1]] = it[2];
adjMat[it[1]][it[0]] = it[2];
}
// Applying Floyd Warshall Algorithm
// For intermediate node k
for (let k = 0; k < n; k++) {
// node i ---> node j
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
adjMat[i][j] =
Math.min(adjMat[i][j],
adjMat[i][k] + adjMat[k][j]
);
}
}
}
// To store the minimum count of neighbors
let minCount = 1e9;
/* To store the answer (city having
smallest number of neighbors) */
let ans;
// Check every city
for (let i = 0; i < n; i++) {
/* To count the neighbors of given city
having distance lesser than threshold */
let count = 0;
// City i ---> City j
for (let j = 0; j < n; j++) {
/* If the distance to reach city j from
city i is less than threshold */
if (i !== j && adjMat[i][j] <= distanceThreshold) {
// Increment count
count++;
}
}
// if current count is less than minimum count
if (count < minCount) {
// Update minimum count
minCount = count;
// Store the answer
ans = i;
}
/* Else if current count is
equal to minimum count */
else if (count === minCount) {
/* Update the answer (to store
city with greater number) */
ans = i;
}
}
// Return the resulting city as answer
return ans;
}
}
// Main function to test the solution
const main = () => {
const N = 4, M = 4;
const edges = [
[0, 1, 3], [1, 2, 1],
[1, 3, 4], [2, 3, 1]
];
const distanceThreshold = 4;
/* Creating an instance of
Solution class */
const sol = new Solution();
/* Function to find the city with
the smallest number of neighbors. */
const ans = sol.findCity(N, M, edges, distanceThreshold);
// Output
console.log("The city with smallest number of neighbors (with given threshold) is:", ans);
};
main();
