ข้อนี้กำหนดให้มีถ้ำที่มี $N$ $(N\leq 2000)$ โถงและทางเชื่อมระหว่างโถง $E$ $(E\leq 10000)$ ทางเชื่อม โดยโจทย์นี้ต้องให้จำลองหาเวลาที่จะใช้เพื่อไปจากโถง $P$ ไปยังโถง $U$ ณ เวลาต่างๆ ในตอนแรกระดับน้ำจะอยู่ที่ $h=0$ แต่ระดับน้ำจะเพิ่มขึ้นเรื่อยๆ และทำให้ระยะเวลาการเดินทางในแต่ละทางเชื่อมเพิ่มขึ้น

แต่ละทางเชื่อมจะไปจากโถง $Q$ ไปยังโถง $R$ และใช้เวลา $T_{Q,R}$ (จะไปจาก $Q$ ไปยัง $R$ เท่านั้น ไม่สามารถไปจาก $R$ ไป $Q$ ด้วยทางเชื่อมเดียวกัน) ในตอนเริ่มคือ $h=0$ เมื่อผ่านไปถึงเวลา $h$ จะกลายเป็น $T_{Q,R}+h$ ยกเว้นทางเชื่อมที่ติดกับ $P$ ซึ่งจะเป็น $T_{Q,R}$ ตลอด

จากนั้นโจทย์จะถามผลการจำลอง $L$ $(L \leq 500000)$ คำถามว่าเวลาที่ใช้เดินทางจาก $P$ ไป $U$ ที่เป็นไปได้ต่ำสุดคือเท่าไหร่เมื่อระดับน้ำคือ $h_i$

แนวคิด

ข้อนี้เป็นโจทย์ Dijkstra

อย่างแรกสังเกตว่าเราไม่จำเป็นต้องกลับมายังจุดเริ่มต้นเพราะเพียงแต่จะทำให้การไปถึง $U$ ช้าลง ดังนั้นจึงสามารถตัดทางเชื่อมใดๆ ที่มีจบออกมายัง $P$

สมมติว่าเส้นทางเดินที่เลือกคือ $P, X_1, X_2, \dots, X_{c-1}, U$ ณ ระดับความสูงน้ำ $h_i$ ระยะเวลาการเดินทางรวมคือ $T_{P, X_1} + (T_{X_1, X_2} + h_i) + (T_{X_2,X_3} + h_i) + \dots + (T_{X_{c-1}, U} + h_i)$ ดังนั้นหากทำ Dijkstra สำหรับทุกการจำลอง $L$ ครั้งจะได้ทำตอบที่ต้องการ แต่ะจะใช้เวลานานเกินไป $\mathcal{O}(L(N + E\log N))$ ซึ่งช้าเกินไป

สังเกตได้ว่า $P, X_1, X_2, \dots, X_{c-1}, U$ จะผ่านทางเชื่อม $c$ ทางเชื่อมและ $T_{P, X_1} + (T_{X_1, X_2} + h_i) + (T_{X_2,X_3} + h_i) + \dots + (T_{X_{c-1}, U} + h_i) = (c-1) h_i + T_{P, X_1} + T_{X_1, X_2} + T_{X_2,X_3} + \dots + T_{X_{c-1}, U}$ ดังนั้นเวลาที่ใช้คือระยะทางที่เวลา $h=0$ บวกกับจำนวนทางเชื่อมที่ผ่านลบ $1$ คูณกับ $h_i$

เราสามารถแปลงกราฟเดิมเป็นกราฟใหม่โดยมองว่าแต่ละจุดยอดใน Graph แทน State ว่าอยู่ที่โถง $x$ และผ่านมาแล้ว $c$ ทางเชื่อม เราไม่ต้องสนใจ State ที่ผ่านไปเกิน $N-1$ ทางเชื่อมเพราะเส้นทางดังกล่าวจะมี Cycle ที่สามารถตัดออกและลดระยะเวลาได้ ดังนั้นจะมี $N^2$ State คือจบที่โถง $x$ ระหว่าง $0$ ถึง $N-1$ และผ่านไปแล้ว $c$ ทางเชื่อมระหว่าง $0$ ถึง $N-1$ ทางเชื่อมในกราฟใหม่จะเพิ่มจากกราฟเก่าที่มี $E$ เป็น $EN$ เพราะจะต้องมีหนึ่งทางเชื่อมสำหรับทุก $c$ ตั้งแต่ะ $0$ ถึง $N-1$

การทำ Dijkstra บนกราฟใหม่นี้จะทำให้ได้ $dist[x][c]$ แทนผลรวม $T_{Q,R}$ ในเส้นทางจาก $P$ ไป $u$ โดยผ่าน $c$ ทางเชื่อมที่ต่ำสุดที่เป็นไปได้ โดย Dijkstra จะใช้เวลา $\mathcal{O}(N^2 + EN \log N))$

Dijkstra จะทำให้ได้คำตอบว่าหากเริ่มที่ $P$ และไปถึง $U$ โดยผ่านไปแล้ว $c$ ทางเชื่อมจะทำให้ผลรวม $dist[U][c] = T_{P, X_1} + T_{X_1, X_2} + T_{X_2,X_3} + \dots + T_{X_{c-1}, U}$ เป็นไปได้ต่ำสุดคือเท่าไหร่

เมื่อเรามี $dist[U][c]$ สำหรับทุก $c$ ตั้งแต่ $1$ ถึง $N-1$ แล้วเราจะสามารถหาคำตอบแต่ละ $h_i$ โดยการไล่ $c$ หาค่า $dist[U][c] + (c-1) h_i$ ที่ต่ำสุดเป็นคำตอบซึ่งจะใช้เวลา $\mathcal{O}(LN)$ ซึ่งพอสำหรับข้อนี้

Dijkstra's Algorithm

Dijkstra's Algorithm เป็นขั้นตอนวิธีที่ใช้หาระยะทางสั้นในกราฟสุดจากจุดยอดเริ่มต้น $S$ ไปยังทุกจุดยอด สมมิตว่ากราฟที่พิจารณามี $N$ จุดยอดและ $E$ ทางเชื่อม

ให้ระยะของเส้นเชื่อมระหว่าง $a$ กับ $b$ เป็น $w_{a,b}$ (สังเกตว่าใน Dijkstra หากมีมากกว่าหนึ่งเส้นเชื่อมระหว่าง $a$ กับ $b$ จะสามารถเลือกอันที่สั้นสุดมาอันเดียวเราจึงสามารถพิจารณาแค่กรณีที่กราฟเป็นกราฟเชิงเดียว (Simple Graph) ซึ่งแปลว่าจาก $a$ ไป $b$ มีอย่างมากเส้นเชื่อมเดียว)

หลักการทำงานของ Dijkstra คือจะเก็บระยะ $dist[i]$ สำหรับแต่ละจุดยอด $i$ ในกราฟซึ่งแทนระยะทางต่ำสุดจาก $S$ ไปยัง $i$ ที่พบแล้ว ในตอนเริ่มต้นจะตั้ง $dist[S]=0$ และ $dist[i]=\infty$ สำหรับ $i\neq S$ จากนั้นในแต่ละขั้นจะเลือกจุดยอด $a$ ที่ยังไม่ได้พิจารณาที่มี $dist[a]$ ต่ำสุด (โดยที่ $a$ ไปถึงได้นั่นคือ $dist[a] \neq \infty$) และพิจารณาแต่ละเส้นเชื่อมออกจาก $a$ ไปยัง $b$ ว่า $dist[a] + w_{a,b}$ ต่ำกว่า $dist[b]$ ในปัจจุบันหรือไม่ หากใช่จะแก้ $dist[b] = dist[a] + w_{a,b}$ (เพราะเป็นเส้นทางที่ผ่าน $a$ ไปถึง $b$ ที่ใช้เวลาดังกล่าว)

ใน Implementation ทั่วไป จะใช้ Binary Heap เพื่อหา $a$ ที่มี $dist[a]$ ต่ำสึดในแต่ละขั้นจนกว่า Heap จะว่าง ซึ่งจะทำให้การแก้ค่า $dist[b]$ และใส่ใน Heap ใหม่ใช้เวลา $\mathcal{O}(\log E)$ และการหาค่าต่ำสุดจะใช้เวลา $\mathcal{O}(\log E)$ เช่นกัน (อ่านเรื่อง Binary Heap เพิ่มได้จาก https://programming.in.th/tasks/1021/solution) สำหรับกราฟเชิงเดียวจะได้ว่า $\mathcal{O}(\log E) = \mathcal{O}(\log N)$ เพราะ $E \leq N^2$

แต่ละทางเชื่อมจะถูกพิจารณาอย่างมากครั้งเดียวดังนั้นการใส่ค่าใหม่ใน Binary Heap จะเกิดขึ้นอย่างมาก $\mathcal{O}(E)$ ครั้ง ซึ่งแปลว่าเวลาที่ใช้กับขั้นตอนวิธีทั้งหมดรวมทั้งการนำเข้าและเอาออกจะเป็น $\mathcal{O}(E \log V)$ เมื่อรวมกับการตั้งค่าเริ่มต้นของ $dist[i]$ สำหรับทุก $i$ จะได้เป็น $\mathcal{O}(V + E\log V)$ สำหรับทั้งขั้นตอนวิธี

โค้ดตัวอย่างสำหรับ Dijkstra ทั่วไป (ดัดแปลงจาก https://usaco.guide/CPH.pdf#page=136)

int dist[MAX];
bool visited[MAX];

vector<pair<int, int>> edges[MAX];

void dijkstra(int N, int S) {
  for (int i = 1; i <= N; i++)
    dist[i] = INF;
  dist[S] = 0;

  priority_queue<pair<int, int>> q;

  q.push({0, S});
  while (!q.empty()) {
    int a = q.top().second;
    q.pop();
    if (visited[a])
      continue;
    visited[a] = true;
    for (auto e : edges[a]) {
      int b = e.first, w = e.second;
      if (dist[a] + w < dist[b]) {
        dist[b] = dist[a] + w;
        q.push({-dist[b], b});
      }
    }
  }
}

โค้ดนี้เก็บเส้นเชื่อมเป็น edges[a] สำหรับทางเชื่อมที่ออกจาก $a$ ด้วย pair<int,int> โดยค่าแรกใน pair จะเป็นอีกปลาย $b$ ของแต่เส้นเชื่อม และค่าที่สองจะเป็นระยะของเส้น $w_{a,b}$

ในโค้ดนี้ใช้std::priority_queue เป็น Heap สังเกตว่าจะใช้ -dist[b] เป็นค่าแรกเพราะ std::priority_queue จะเอาค่ามาสุดมาก่อน การใช้ค่าติดลบจึงทำให้เอาค่า dist ที่ต่ำสุดมาก่อนตามที่ต้องการ

Dijkstra สำหรับข้อนี้

สำหรับข้อนี้จะต้องแปลงให้แต่ละจุดยอดในกราฟเก็บทั้งหมายเลขของโถง $x$ และจำนวน $c$ เพื่อให้เป็น State ตามที่อธบิายไว้

ดังนั้นจะต้องแก้ให้ dist และ visited ให้เป็น Array 2 มิติ และใน priority_queue จะต้องเป็น State เป็น pair ของค่าแทนที่จะเป็นค่าเดียว

long long dist[MAX][MAX];
int visited[MAX][MAX];

vector<pair<int, int>> edges[MAX];

void dijkstra(int N, int S) {
  priority_queue<pair<int, pair<int, int>>> q;

  for (int i = 0; i <= N; i++)
    for (int j = 0; j <= N; j++)
      dist[i][j] = 1000000000000000000LL, visited[i][j] = false;

  dist[S][0] = 0;
  q.push({-0, {S, 0}});

  while (!q.empty()) {
    int a = q.top().second.first;
    int c = q.top().second.second;
    q.pop();

    if (visited[a][c])
      continue;

    visited[a][c] = true;

    if (c >= N) // ไม่ต้องพิจารณาไปต่อถ้า State ปัจจุบันผ่านมาแล้ว N ทางเชื่อม
      continue;

    for (auto e : edges[a]) {
      int b = e.first, w = e.second;
      if (dist[b][c + 1] > dist[a][c] + w) {
        dist[b][c + 1] = dist[a][c] + w;
        q.push({-dist[b][c + 1], {b, c + 1}});
      }
    }
  }
}