ক্ষুদ্রতম পথ: 20টি প্রান্ত
fx-50FH II · CMPLX · 637 bytes
সর্বোচ্চ দশটি শীর্ষ ও 20টি প্রান্তের অনির্দেশিত নেটওয়ার্কে ন্যূনতম খরচের একটি পথ বের করুন; শীর্ষগুলি ক্রমে, শেষে মোট খরচ দেখায়।
- ৬৩৭ বাইট
- CMPLX মোড
সমাধানসহ উদাহরণ
উদাহরণ ১
বিশ্ববিদ্যালয়ের অপারেশনস রিসার্চের মৌলিক অনুশীলন: জাদুঘরের রোবট নম্বরযুক্ত কক্ষে চলাচল করে। সংযোগ দ্বিমুখী, খরচ মিনিটে। 2 থেকে 6-এর সর্বনিম্ন সময়ের পথ ও মোট সময় বের করুন।
সব প্রান্ত অনির্দেশিত; তালিকার বাইরের সংযোগ নেই। তালিকা (a–b: খরচ): 2–1: 7; 2–3: 4; 1–4: 5; 3–4: 2; 3–5: 8; 4–6: 3; 5–6: 2; 1–5: 12
উত্তর
মানক সমাধান (ক্যালকুলেটর ছাড়া)
- S থেকে Dijkstra চালান। u সদ্য নির্ধারিত শীর্ষ, d(v) হালনাগাদ অস্থায়ী দূরত্ব, ∞ এখনও অপ্রাপ্য।
- u=2, d(2)=0; d(1)=7, d(3)=4
- u=3, d(3)=4; d(4)=6, d(5)=12
- u=4, d(4)=6; d(6)=9
- u=1, d(1)=7; ∅
- u=6, d(6)=9; d(5)=11
- পূর্বসূরি থেকে পথ ফিরে সরাসরি খরচ যোগ করুন: 2 → 3 → 4 → 6; মোট খরচ 4+2+3=9 min
উদাহরণ ২
বিশ্ববিদ্যালয়ের অপারেশনস রিসার্চের মৌলিক অনুশীলন: প্রদর্শনীর শাটল নেটওয়ার্কে পূর্ণসংখ্যায় ভাড়া। 7–8 সংযোগ বিনামূল্যে, খরচ ঠিক 0। 7 থেকে 2-এর সর্বনিম্ন ভাড়ার পথ ও মোট ভাড়া বের করুন।
সব প্রান্ত অনির্দেশিত; তালিকার বাইরের সংযোগ নেই। তালিকা (a–b: খরচ): 7–8: 0; 8–9: 3; 9–2: 4; 7–1: 9; 1–2: 2; 8–2: 10; 9–1: 1
উত্তর
মানক সমাধান (ক্যালকুলেটর ছাড়া)
- S থেকে Dijkstra চালান। u সদ্য নির্ধারিত শীর্ষ, d(v) হালনাগাদ অস্থায়ী দূরত্ব, ∞ এখনও অপ্রাপ্য।
- u=7, d(7)=0; d(1)=9, d(8)=0
- u=8, d(8)=0; d(2)=10, d(9)=3
- u=9, d(9)=3; d(1)=4, d(2)=7
- u=1, d(1)=4; d(2)=6
- u=2, d(2)=6; ∅
- পূর্বসূরি থেকে পথ ফিরে সরাসরি খরচ যোগ করুন: 7 → 8 → 9 → 1 → 2; মোট খরচ 0+3+1+2=6
উদাহরণ ৩
বিশ্ববিদ্যালয়ের অপারেশনস রিসার্চের মৌলিক অনুশীলন: প্রশিক্ষণ যোগাযোগ নেটওয়ার্ক দশটি ভার্চুয়াল টার্মিনাল যুক্ত করে। প্রতিটি দ্বিমুখী সংযোগের স্থির পূর্ণসংখ্যা প্রেরণ খরচ আছে। শেষের সংযোগসহ সব 20টি তালিকার ক্রমে দিয়ে 1 থেকে 10-এর ন্যূনতম খরচের পথ ও মোট খরচ বের করুন।
সব প্রান্ত অনির্দেশিত; তালিকার বাইরের সংযোগ নেই। তালিকা (a–b: খরচ): 1–2: 5; 2–3: 7; 3–4: 4; 4–5: 6; 5–6: 3; 6–7: 8; 7–8: 2; 8–9: 5; 9–10: 4; 1–6: 9; 2–7: 9; 3–8: 9; 4–9: 9; 5–10: 9; 2–9: 1; 1–4: 1; 4–7: 1; 7–10: 1; 1–8: 9; 3–10: 8
উত্তর
মানক সমাধান (ক্যালকুলেটর ছাড়া)
- S থেকে Dijkstra চালান। u সদ্য নির্ধারিত শীর্ষ, d(v) হালনাগাদ অস্থায়ী দূরত্ব, ∞ এখনও অপ্রাপ্য।
- u=1, d(1)=0; d(2)=5, d(4)=1, d(6)=9, d(8)=9
- u=4, d(4)=1; d(3)=5, d(5)=7, d(7)=2, d(9)=10
- u=7, d(7)=2; d(8)=4, d(10)=3
- u=10, d(10)=3; d(9)=7
- পূর্বসূরি থেকে পথ ফিরে সরাসরি খরচ যোগ করুন: 1 → 4 → 7 → 10; মোট খরচ 1+1+1=3
কখন ব্যবহার করবেন
বিশ্ববিদ্যালয় গণিত · অপারেশনস রিসার্চ। স্থির নেটওয়ার্কে অঋণাত্মক ও যোগযোগ্য খরচের জন্য। বাস্তব দিক বা যাত্রার শর্ত নিজে নির্ধারণ করে না।
নেটওয়ার্ক লিখুন
- প্রথম Y?-এ S+Ti দিন: S শুরু ও T গন্তব্য। পরে পালাক্রমে Y?-এ অনির্দেশিত প্রান্ত a+bi, M?-এ খরচ দিন। i-এর জন্য ENG। শীর্ষ বা প্রান্তের সংখ্যা আলাদা করে দেবেন না।
- শেষ করতে পরের Y?-এ শুধু EXE, তারপর M?-এ শুধু EXE চাপুন। দুটি ভিন্ন প্রশ্ন। জানা শূন্য খরচ লিখতে 0EXE দিন।
পথ ও খরচ পড়ুন
- প্রতি Disp পর্দায় S থেকে একটি পথের শীর্ষ দেখায়। T-সহ প্রতিটি শীর্ষের পরে EXE চাপলে শেষে মোট খরচ আসে। −1 মানে পথ নেই। S=T হলে S, তারপর 0। শেষে AC দিয়ে বের হন; EXE আবার চালায়।
শর্ত ও সীমা
- শীর্ষ নম্বর পূর্ণসংখ্যা 1–10, খরচ পূর্ণসংখ্যা 0–100; সর্বোচ্চ 20টি স্ব-লুপবিহীন প্রান্ত। সমান্তরাল প্রান্ত প্রতিটি একটি স্থান নেয়। সব খরচের একক একই রাখুন।
- 20-প্রান্ত সংস্করণ প্রান্তবিন্দু ও খরচের পূর্ণসংখ্যা এবং সীমা যাচাই করে। একটি ঘর ফাঁকা, অবৈধ মান বা অতিরিক্ত প্রান্তে Math ERROR। জায়গা থাকলে বৈধ স্ব-লুপ উপেক্ষিত; পূর্ণ হলে শুধু দুই ফাঁকা উত্তরে শেষ হয়।
- যৌথ 680 bytes-এর 637 bytes ব্যবহৃত হয়, অন্য স্লটে 43 bytes থাকে। প্রতি চালনায় A, B, C, D, X, Y, M ও Ans মুছে যায়; দরকারি মান আগে রাখুন।
- CMPLX, a+bi, Norm 1-এ তৈরি ও চালান। উদাহরণে Deg ও P1। স্বাভাবিক সমাপ্তিতে Norm 1 ফেরে। i দুটি পূর্ণসংখ্যা নম্বর মেলায়, কাল্পনিক খরচ নয়।
- নির্দেশিত প্রান্ত, ঋণাত্মক ওজন ও দশের বেশি শীর্ষ সমর্থিত নয়। সমান খরচে একটি পথই দেয়; সর্বনিম্ন প্রান্তসংখ্যার নিশ্চয়তা নেই। সীমিত নির্ভুলতার ব্যবধান কম, তাই কোড হুবহু রাখুন।
প্রবেশাধিকার যাচাই হচ্ছে…