[ UVa ] 11463 - Commandos

• এই সমস্যা টা মিনি-ম্যাক্স টাইপের সমস্যা । 
• এই সমস্যা সমাধান করার জন্য প্রথমে আমাদের কে প্রত্যেক বিল্ডিং থেকে প্রত্যেক বিল্ডিং এ যাওয়ার মিনিমাম পাথ বের করতে হবে এই জন্য আমরা Floyd Warshall ব্যবহার করতে পারি । 
• এর পর আমাদের কে যে source ও destination দেয়া থাকবে । 
• আমরা প্রত্যেক বার source থেকে i হয়ে destination এ যেতে চেষ্টা করবে । যদি আমরা যতগুলি i ব্যবহার করে আমাদের লক্ষ্যে যেতে পারব তাদের মধ্যে যেটা ম্যাক্সিমাম সেটাই আমাদের কে প্রিন্ট করতে হবে ।  

কোড :

	/**
	* Problem : 11463 - Commandos.
	* Verdict : Accepted.
	* Writer : Mehadi Hasan Menon.
	* Time : 0.010 ms.
	***/
	#include <iostream>
	using namespace std;
	const int mx = 105;
	const int inf = 1000007;
	int quarter[mx][mx];
	void floyd(int n)
	{
	for(int k = 0; k < n; k++)
	{
	for(int i = 0; i < n; i++)
	{
	for(int j = 0; j < n; j++)
	{
	quarter[i][j] = min(quarter[i][j], quarter[i][k] + quarter[k][j]);
	}
	}
	}
	}
	int main()
	{
	freopen("input.txt", "r+", stdin);
	int tc, n, r;
	scanf("%d", &tc);
	for(int t = 1; t <= tc; t++)
	{
	scanf("%d %d", &n, &r);
	for(int i = 0; i < n; i++)
	{
	for(int j = 0; j < n; j++)
	{
	quarter[i][j] = quarter[j][i] = inf;
	if(i == j) {
	quarter[i][j] = 0;
	}
	}
	}
	int u, v;
	for(int i = 0; i < r; i++)
	{
	scanf("%d %d", &u, &v);
	quarter[u][v] = quarter[v][u] = 1;
	}
	floyd(n);
	int ans = 0;
	scanf("%d %d\n", &u, &v);
	for(int i = 0; i < n; i++)
	{
	if(quarter[u][i] != inf && quarter[i][v] != inf) {
	ans = max(ans, quarter[u][i] + quarter[i][v]);
	}
	}
	printf("Case %d: %d\n", t, ans);
	}
	return 0;
	}

view raw 11463.cpp hosted with ❤ by GitHub