โปรแกรม C++ เพื่อค้นหาระยะเวลาขั้นต่ำที่จำเป็นในการเข้าถึงจากต้นทางไปยังสถานีปลายทางโดยรถไฟ

สมมติว่า n สถานีเชื่อมต่อกันด้วย m แทร็ค สถานีมีชื่อตั้งแต่ 1 ถึง n รางรถไฟเป็นแบบสองทิศทาง และเราต้องไปถึงสถานีปลายทางจากสถานี src สถานีต้นทางและปลายทางของทางรถไฟสายที่ i อยู่ในอาร์เรย์ 'ถนน' โดยที่ถนน[i] อยู่ในรูปแบบ {station1, station2} จากสถานี j-th รถไฟจะออกสำหรับทุกสถานีที่เชื่อมต่อกับสถานีที่เวลาทวีคูณ kj และรถไฟแต่ละขบวนจะใช้เวลาประมาณ tj เพื่อไปถึงปลายทาง ค่าจะได้รับในอาร์เรย์ 'ออกเดินทาง' โดยที่แต่ละองค์ประกอบอยู่ในรูปแบบ {tj, kj} ตอนนี้ เราต้องหาเวลาขั้นต่ำที่เป็นไปได้ในการเข้าถึงจาก src ไปยังปลายทาง เราสามารถเปลี่ยนรถไฟได้หลายขบวน และเวลาที่ใช้ในการเปลี่ยนขบวนนั้นน้อยมาก

ดังนั้น หากอินพุตเป็น n =4, m =3, src =1, dst =4, roads ={{1, 2}, {2, 4}, {3, 4}}, exit ={{2 , 1}, {3, 5}, {7, 6}} แล้วผลลัพธ์จะเป็น 8

จากสถานี 1 เรานั่งรถไฟไปสถานี 2 เวลา 0 เวลาไปถึงสถานี 2 ได้ 2 จากสถานี 2 เรานั่งรถไฟไปสถานี 4 เวลา 5. เวลาที่ไปถึงสถานี 2 เท่ากับ 3 ทั้งหมด เวลาที่ใช้คือ (5 + 3) =8.

ขั้นตอน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

src :=src - 1dst :=dst - 1Define a new array graph[n] ที่มี tuplesfor initialize i :=0 when i  dp[b] แล้ว:dp[b] :=weight insert pair(weight, b) ที่ส่วนท้ายของ priqreturn -1

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include ใช้เนมสเปซ std;int แก้ปัญหา (int n, int m, int src, int dst, vector> roads, vector> ออกเดินทาง){ src -=1; dst -=1; vector> กราฟ[n]; int a, b; int เสื้อ k; for(int i =0; i  dp(n, -9999); Priority_queue> priq; dp[src] =0; priq.push(make_pair(-dp[src], src)); int w; ในขณะที่ (ไม่ใช่ priq.empty ()) { เสมอ (w, a) =priq.top (); priq.pop(); if(a ==dst){ return -w; } if(w  dp[b]){ dp[b] =น้ำหนัก; priq.push(make_pair(น้ำหนัก b)); } } } return -1;}int main() { int n =4, m =3, src =1, dst =4; vector> roads ={{1, 2}, {2, 4}, {3, 4}}, ออกเดินทาง ={{2, 1}, {3, 5}, {7, 6 }}; cout<<แก้ (n, m, src, dst, ถนน, ออกเดินทาง); คืนค่า 0;}

อินพุต

ผลลัพธ์

8