Dijkstra Algorithm

 
#include
#include
#define inf 1000000000
#define SIZE1 20000
#define SIZE2 50000
using namespace std;
typedef vectorgraph;
long Q[SIZE1+9],d[SIZE1+9],positionOf[SIZE1+9];
graph G[SIZE2*2+9],W[SIZE2*2+9];
//posiotionOf[]= posiontion of one node in Q[] or tree
//Q[] is a tree or collection of nodes in priority sequences.
//d[]= the minimum values to reach in nodes. 

int min_heapify(long i,long n){
	long temp,minimum,l,r;
	l=2*i;
	r=2*i+1;
	if(l<=n && d[Q[l]]d[Q[i]]){
			temp=Q[i/2];
			Q[i/2]=Q[i];
			Q[i]=temp;		
			positionOf[Q[i]]=i;
			positionOf[Q[i/2]]=i/2;		
			i=i/2;
		}
		else
			break;		
	}
	return 0;
}
int main(){
	long i,j,n,m,u,v,w,source,dest,t;	
	scanf("%ld",&t);
	for(j=1;j<=t;j++){		
		scanf("%ld%ld%ld%ld",&n,&m,&source,&dest);
		for(i=1;i<=n;i++){
			G[i].clear();
			W[i].clear();
			d[i]=inf;
			Q[i]=i;
			positionOf[i]=i;
		}
		for(i=1;i<=m;i++){
			scanf("%ld%ld%ld",&u,&v,&w);
			G[u+1].push_back(v+1);
			G[v+1].push_back(u+1);
			W[u+1].push_back(w);
			W[v+1].push_back(w);
		}		
		d[source+1]=0;update_min_heap(source+1);
		while(n>0)
		{
			u=extract_min_Q(n);
			n--;
			for(v=0;v1)
					{
						update_min_heap(positionOf[G[u][v]]);
					}

				}
			}			
		}		
		if(d[dest+1]==inf)
			printf("Case #%ld: unreachable\n",j);
		else
			printf("Case #%ld: %ld\n",j,d[dest+1]);
	}
	return 0;
}

About This Blog

This Blog is only for myself.

প্রজাপতির অস্বাভাবিক পরিবর্তন

জাপানে তেজস্ক্রিয় পদার্থের মিশ্রণের প্রভাব পড়েছে পরিবেশের ওপর। দেশটিতে বিকারগ্রস্ত প্রজাপতির অস্তিত্ব পাওয়া গেছে। ফুকুশিমা পারমাণবিক দুর্ঘটনার পর সংগৃহীত প্রজাপতি গবেষণা করে এর প্রমাণ মিলেছে।

গবেষণায় দেখা গেছে, প্রজাপতির অস্বাভাবিক পরিবর্তন। বৃদ্ধি পেয়েছে বিকারগ্রস্ত পা, শুঙ্গ ও পাখার সংখ্যা। আর বিকারগ্রস্ত এসব প্রজাপতির সঙ্গে তেজস্ক্রিয় পদার্থের সম্পর্ক রয়েছে। গবেষণার ফল সায়েন্টিফিক রিপোর্টস সাময়িকীতে প্রকাশ করা হয়েছে।২০১১ সালের মার্চে ভয়াবহ সুনামির জেরে ফুকুশিমা পরমাণু বিদ্যুৎ প্রকল্পে বিপর্যয়ের পরপরই ওই এলাকায় শুককীট (প্রজাপতির জীবন চক্রের প্রথম পর্যায়) অবস্থায় শতকরা ১২ ভাগ প্রজাপতির মধ্যে অস্বাভাবিক পরিবর্তন লক্ষ্য করা গেছে। ঘটনার দুই মাস পর জাপানি গবেষকেরা ফুকুশিমাসহ ১০টি স্থান থেকে একটি নির্দিষ্ট প্রজাপতির ১৪৪টি প্রাপ্তবয়স্ক প্রজাপতি সংগ্রহ করেন। দুর্ঘটনার সময় জীবনচক্রের প্রথম ধাপে ছিল সাধারণত এমন প্রজাপতিই সংগ্রহ করা হয়। গবেষণায় দেখা যায়, তেজস্ক্রিয় পদার্থের প্রভাব বেশি পড়েছে—এমন এলাকার প্রজাপতির পাখা তুলনামূলক অনেক ছোট এবং এর চোখের বৃদ্ধিও ঘটেছে অসমভাবে।দুর্ঘটনার ছয় মাস পর আবার ওই ১০টি স্থান থেকে প্রজাপতি সংগ্রহ করা হয়। এগুলো গবেষণা করে দেখা যায়, ফুকুশিমা থেকে সংগৃহীত প্রজাপতির বিকারের মাত্রা দুর্ঘটনার দুই মাস পর সংগ্রহ করা প্রজাপতির বিকারের চেয়ে দ্বিগুণেরও বেশি। গবেষক দলের প্রধান ওকিনাওয়ার ইউনিভার্সিটি অব রিউকিউসের অধ্যাপক জজি ওতাকি বলেন, ‘এটা সব সময়ই ধরে নেওয়া হতো যে, কীটপতঙ্গ হচ্ছে তেজস্ক্রিয় প্রতিরোধকারী। ওই ধারণা অনুযায়ী, আমাদের গবেষণার ফল হয়েছে অপ্রত্যাশিত।’গবেষকেরা বলেন, দূষিত খাদ্যের ফলে প্রজাপতির বিকার হয়েছে। অথচ এসব প্রজাপতির পূর্ববর্তী প্রজন্মে এ ধরনের কোনো বিকার ছিল না।গবেষক দলটি ১০ বছরেরও বেশি সময় ধরে এই নির্দিষ্ট প্রজাতির প্রজাপতি নিয়ে গবেষণা করছেন। পরিবেশগত পরিবর্তন এই প্রজাতির ওপর ব্যাপকভাবে প্রভাব ফেলে। নতুন গবেষণার মাধ্যমে এটাই প্রতীয়মান হয়েছে, প্রাণীকূলের ওপর ফুকুশিমা দুর্ঘটনার প্রভাব এখনো পড়ছে। তেজস্ক্রিয়তার মাত্রা কমে এলেও প্রাণীকূল প্রভাবিত হচ্ছে। বিবিসি।

মঙ্গলে নামল কিউরিওসিটি

অবশেষে সব উৎকণ্ঠার অবসান ঘটিয়ে মঙ্গলে নামল নাসার রোবট যান রোভার কিউরিওসিটি। গতকাল সোমবার গ্রিনিচ মান সময় ভোর পাঁচটা ৩২ মিনিটে (বাংলাদেশ সময় বেলা সাড়ে ১১টা) লাল গ্রহটিতে সফলভাবে অবতরণ করে মাকড়সা আকৃতির এ যানটি।  

মঙ্গল গবেষণার ইতিহাসে এটিই এখন পর্যন্ত নাসার বিজ্ঞানীদের সবচেয়ে বড় সাফল্য। রোবট যানটির ওজন প্রায় এক টন। এই প্রথম নাসা এত বেশি ওজনের যান কোনো গ্রহে সফলভাবে নামাতে সক্ষম হলো। 

কিউরিওসিটির মঙ্গলে অবতরণ নিয়ে উৎকণ্ঠ ছিল নাসার বিজ্ঞানীদের মধ্যে। তাই কিউরিওসিটির অবতরণের ঘোষণার পর মার্কিন মহাকাশ গবেষণা সংস্থার (নাসা) জেট প্রপালশন ল্যাবরেটরির বিজ্ঞানীরা উল্লাসে ফেটে পড়েন। প্রধান বিজ্ঞানীরা ‘মার্স চকোলেট’ বার নাসার কর্মীদের মধ্যে বিতরণ করেন। 

নাসার প্রশাসক চার্লস বোল্ডেন বলেন, ‘আমরা আবারও মঙ্গলে—এটা সত্যিই অবিশ্বাস্য! এর চেয়ে ভালো কিছু হতে পারে না। 

কিউরিওসিটির পাঠানো প্রথম ছবিটি ধূসর। তাতে রোভারের চাকা মঙ্গলের মাটি স্পর্শ করার দৃশ্য দেখা গেছে। কয়েক সেকেন্ডের ব্যবধানে দ্বিতীয় ছবি পাঠায় রোভার, তাতে রয়েছে মঙ্গলে রোভারের ছায়া। 

মঙ্গলের আবহাওয়া মন্ডলে প্রবেশের আগ মুহূর্তে মহাকাশ যানটির গতি ছিল ঘণ্টায় ১৩ হাজার ২০০ মাইল। প্রথমে সুপারসনিক প্যারাসুটের সাহায্যে গতি কমানো হয়। পরে গতি আরো নিয়ন্ত্রণে আনা হয়। এরপর ক্রেনের মাধ্যমে ধীরে ধীরে ছয় চাকায় ভর করে ভূমিতে নামে রোভার। এ সময় এটির গতি ছিল সেকেন্ডে মাত্র শূন্য দশমিক ৬ মিটার। অবতরণের জন্য আগেই গিরিখাদ গেইল কার্টার বেছে নেওয়া হয়েছিল। এখানে অতীতে পানি থাকার অনেক চিহ্ন পাওয়া গেছে। আগামী দুই বছর কিউরিওসিটি গিরিখাদের তলা থেকে ধীরে ধীরে ওপরে উঠবে। এটি পাথুরে ভূমি খুঁড়ে দেখবে, সেখানে প্রাণের বিকাশের কোনো পরিবেশ আছে কি না। 

মঙ্গলে অবস্থানকালে পারমাণবিক শক্তিতে চলবে কিউরিওসিটি। এটি নানা বৈজ্ঞানিক যন্ত্রপাতিতে ঠাসা। আছে ক্যামেরা, আবহাওয়া নিরীক্ষণ কেন্দ্র, শক্তিশালী ড্রিলসহ রোবটিক হাত, দূর থেকে পাথর চূর্ণ-বিচূর্ণ করতে সক্ষম লেজার, রাসায়নিক গবেষণাগার ও বিকিরণ মাপার যন্ত্র। 

কিউরিওসিটি মঙ্গলে মানুষ কিংবা জীবের অস্তিত্ব খুঁজে পাবে—এমনটা প্রত্যাশা করছেন না বিজ্ঞানীরা। তবে তাঁরা আশা করছেন, এটির সাহায্যে মঙ্গলের মাটি ও পাথর গবেষণা করে তাঁরা জানতে পারবেন, সেখানে অতীতে প্রাণীর অস্তিত্ব ছিল কি না। এ ছাড়া ভবিষ্যতে মানুষের যাওয়ার উপযোগী পরিবেশ আছে কি না, তা-ও গবেষণা করে দেখা হবে। 

২০১১ সালের নভেম্বর মাসে ফ্লোরিডার কেপ ক্যানাভারেল থেকে যাত্রা শুরু করে কিউরিওসিটি। সাড়ে আট মাসের এই অভিযানে যানটি এরই মধ্যে বিকিরণের ওপর নানা তথ্য সংগ্রহ করেছে। মঙ্গলের পথে কিউরিওসিটি ৩৫ কোটি ২০ লাখ মাইল পাড়ি দিয়েছে। ১২ বছরের প্রস্তুতি শেষে এ প্রকল্পে ব্যয় হয়েছে ২৫০ কোটি ডলার। 

১৯৬০ সাল থেকে সারা বিশ্বের মহাকাশ গবেষণা সংস্থাগুলোর মঙ্গল গ্রহে বেশির ভাগ অভিযানই ব্যর্থ হয়েছে। সফলতার হার প্রায় ৪০ শতাংশ। অধিকাংশ ক্ষেত্রেই ধূলিঝড় বা যান্ত্রিক ত্রুটির মতো প্রতিকূলতায় পড়তে হয়েছে বিজ্ঞানীদের। 

বিবিসি ও এএফপি।

ফেসবুকের ছায়াবন্ধু, নাকি সামনের কায়াবন্ধু

ড. মুহম্মদ জাফর ইকবাল আমাকে একট গল্প শুনিয়েছেন। গল্প নয়, সত্য ঘটনা। চীনের এক দম্পতি কম্পিউটারে এক নতুন খেলা পেয়েছেন। একটা বাচ্চাকে লালন-পালন করতে হয়। তাঁরা সারাক্ষণ কম্পিউটার নিয়ে পড়ে থাকেন। এই বাচ্চাকে খাওয়ান, পরান, গোসল করান। এই বাচ্চার প্রতি তাঁদের যত্নের সীমা নেই। তাঁরা একেবারেই মগ্ন হয়ে গেলেন। কিন্তু তাঁদের নিজেদের একটা বাচ্চা ছিল। খেলায় মগ্ন এই দম্পতি নিজেদের বাচ্চার কথা ভুলে গেলেন। একদিন দেখা গেল, বাচ্চাটা মরে পড়ে রয়েছে।

২.
জ্যাক দেরিদা রুশোর স্বীকারোক্তিমূলক আত্মজীবনী কনফেশনস থেকে উদাহরণ দিয়ে বলেছিলেন, প্রতীক বা বিকল্প কখনো কখনো নিজেই প্রধান হয়ে ওঠে। রুশো কৈশোরে যে বাড়িতে থাকতেন, সেই গৃহকর্ত্রীকে তিনি খুব ভালোবাসতেন। সেই ম্যাডাম যে বিছানায় শুতেন, রুশো সেই বিছানাকে চুমু দিতেন, আদর করতেন তাঁর চেয়ারকে, মেঝেকে, পর্দাকে। কারণ, ওসব ছিল তাঁর ম্যাডামের বিকল্প। সামনে ম্যাডাম নেই, কিন্তু এসব বস্তুর মাধ্যমে রুশো তাঁর ম্যাডামের অভাব পূরণ করছেন। কিন্তু একদিন ম্যাডাম তাঁর সামনে, খাচ্ছেন। রুশো বললেন, খাবারে একটা চুল। ম্যাডাম খাবারটা মুখ থেকে বের করতেই রুশো সেই খাবার নিজের মুখে পুরলেন।
এখানে তো ম্যাডাম সামনে আছে, তাহলে কেন রুশো ম্যাডামের মুখের খাবার মুখে পুরলেন।
ম্যাডাম, যাঁকে রুশো বলতেন ম্যামান, তিনি ছিলেন রুশোর মায়ের বিকল্প। তারপর মায়ের চেয়ে ম্যাডামই মুখ্য হয়ে উঠলেন। তারপর ম্যাডামের চেয়ে বিভিন্ন বিকল্পই মুখ্য হয়ে উঠল।
দেরিদা দেখিয়েছেন, এভাবে বিকল্পই প্রধান হয়ে ওঠে।
দেরিদার বক্তব্য হলো, লেখা মুখের কথার বিকল্প নয়, পরিপূরক নয়, লেখাই আসল। টেক্সটই আসল। আমরা কি সেই যুগে প্রবেশ করলাম, যেখানে বাস্তবের চেয়েও বড় হয়ে উঠেছে ভারচুয়াল বাস্তবতা, যেখানে রক্ত-মাংসের বন্ধুর চেয়েও বড় হয়ে উঠেছে স্ক্রিনে দেখা (ও পড়া) ছায়াবন্ধুটি?
সুমনা শারমীন লিখেছিলেন, মা পাশের ঘরে অসুস্থ পড়ে আছেন দিন সাতেক ধরে, ছেলে একবারও তাঁকে দেখতে যায়নি, কিন্তু ফেসবুকে স্ট্যাটাস দিচ্ছে, প্রে ফর মাই মাদার, শি ইজ সিক। মাদার, গেট ওয়েল সুন।

৩.
প্রযুক্তি, যোগাযোগের বিকল্প মাধ্যমগুলো আমাদের কাছে জ্যান্ত মানুষের চেয়ে বড় হয়ে উঠছে কি না?
আমার সামনে আমার বন্ধু বসে আছেন, মা বসে আছেন, বাবা বসে আছেন, ডাক্তার বসে আছেন, এই সময় মোবাইল ফোন বেজে উঠল। আমরা সেটা আগে ধরাটাকেই কর্তব্য বলে মনে করি।
আমার জলজ্যান্ত বন্ধু সামনে বসে আছে, কিন্তু তাকে রেখে আমি ফেসবুকে স্ট্যাটাস দিই, আমি এখন বন্ধুর সঙ্গে কফি খাচ্ছি। 
পাঁচজন স্কুলবন্ধু, তাঁদের দেখা হলো আজ ২২ বছর পরে, তাঁরা আজ একটা জায়গায় একত্র হচ্ছেন, কী ভীষণ উত্তেজনা তাঁদের মধ্যে। দেখা হওয়ার পরে পাঁচজনই পাঁচটা স্ক্রিনের দিকে তাকিয়ে আছেন, কেউ ফেসবুক করছেন, কেউ বা গেমস খেলছেন, কেউ বা খুদেবার্তা পাঠাচ্ছেন, কেউ বা জরুরি ই-মেইল সেরে নিচ্ছেন, কেউ বা চ্যাট করছেন দূরবর্তী কারও সঙ্গে।
সামনে সমুদ্র, একটু পরে অস্ত যাবে সূর্য, সেদিকে খেয়াল নেই। আমি স্ট্যাটাস দিচ্ছি, আহ্, লাইফ ইজ বিউটিফুল, আই অ্যাম ইন আ প্যারাডাইস।
প্রেমিক দেখা করতে গেছে প্রেমিকার সঙ্গে, কোনো নির্জন জায়গায়। দুজনের হাতে দুটো মোবাইল ফোন, দুজনেই নিজ নিজ ফোন নিয়ে ব্যস্ত, সারাক্ষণ বুড়ো আঙুল চলছে।
আমি মহাসড়কে মোটরসাইকেল চালাতে চালাতে একজন পথিককে এসএমএস করতে দেখেছি।
আমি বিয়ের আসরে বসা বরকে এবং বউকে দেখেছি, ফেসবুকে স্ট্যাটাস দিচ্ছেন।

৪.
একটা কৌতুক ছিল। একজন সম্ভাব্য পাত্র ঘটককে বলল, আমি এমন একজনকে বিয়ে করতে চাই, যে কিনা আমাকে আমার ইচ্ছামতো বিনোদন দেবে, আমি চাইলে সে কথা বলা বন্ধ করবে, চাইলেই গান গাইবে, বা নাচবে, বা কথা বলবে, আবার আমি যখন চাইব তখনই সে ঘুমিয়ে পড়বে, আমি চাইলেই সে অন হবে, আমি চাইলেই সে অফ হবে।
ঘটক বললেন, ভাই, আপনি একটা টেলিভিশনকে বিয়ে করুন।
এই কৌতুককে আধুনিকায়ন করে বলা যায়, ভাই, আপনি একটা ইন্টারনেটকে বিয়ে করুন।
কিন্তু তা বলা যাবে বলে মনে হচ্ছে না। কারণ, আমি চাইলে ইন্টারনেট অফ হবে বটে, কিন্তু আমার চাইবার শক্তি যে থাকবে না। রাতের বেলা ঘুমের মধ্যে মনে হবে, যাই না, একটু ফেসবুকটা চেক করি, দেখি না স্ট্যাটাসে কয়টা লাইক পড়ল।

৫.
এই কৌতুক আগেও শুনেছেন। আবার শুনতে পারেন, এই সময়ের শ্রেষ্ঠ কৌতুক।
গৃহপরিচারিকা কয়েক দিন বিনা নোটিশে অনুপস্থিত থাকল। তারপর কাজে ফিরে এলে গৃহকর্ত্রী তাকে বললেন, তুমি কয়েক দিন কাজে আসোনি, ব্যাপার কী?
‘দেশে গেছিলাম, আপা।’
‘দেশে গেছ। বলে যাবা না?’
‘ক্যান? আমি ফেসবুকে স্ট্যাটাস দিছিলাম, তিন দিনের জন্য বাড়ি যাচ্ছি, আপনে দেখেন নাই?’
‘ওমা! তোমার আবার ফেসবুকও আছে নাকি?’
‘কেন? আপনি জানেন না? আপনার বর তো আমার স্ট্যাটাসে কমেন্ট দিছে: মিস ইউ।’

৬.
তলস্তয়ের থ্রি কোশ্চেনস গল্পে পড়েছিলাম—
‘সবচেয়ে গুরুত্বপূর্ণ সময় কী?’
‘এখন। এই মুহূর্ত।’
‘সবচেয়ে গুরুত্বপূর্ণ কাজ কী?’
‘এখন যা করছি।’
‘সবচেয়ে গুরুত্বপূর্ণ মানুষ কে?’
‘যিনি এখন আমার সামনে বসে আছেন।’
প্রিয় পাঠক, আমাদের মনে হয় তলস্তয়ের এই গল্পটা আরেকবার গভীরভাবে ভেবে দেখতে হবে। এই সময়টাই সবচেয়ে গুরুত্বপূর্ণ সময়, এখন যা করছি, এই কাজটাই সবচেয়ে গুরুত্বপূর্ণ কাজ, আর এখন যিনি আমার সামনে আছেন তিনিই সবচেয়ে গুরুত্বপূর্ণ মানুষ। আপনার সামনে রক্ত-মাংসের যে মানুষটি আছেন, তাঁর কথাই নিশ্চয়ই তলস্তয় বলেছেন, দূরবর্তী শত শত ছায়াবন্ধুর কথা নিশ্চয়ই তিনি বোঝাতে চাননি।

আনিসুল হক: সাহিত্যিক ও সাংবাদিক।