[NEW] Add solution for Flight Discount

[vingoel26]

🎯 Problem Information

• Problem Name: Flight Discount
• CSES Link: https://cses.fi/problemset/task/1195
• Category: Graphs / Shortest Path (Dijkstra’s Algorithm)
• Estimated Difficulty: Medium

---

📋 Problem Description

You are given a directed weighted graph with n cities (nodes) and m flights (edges).

• You must find the minimum total cost to travel from city 1 (Syrjälä) to city n (Metsälä).
• You have one discount coupon, which can be used on exactly one flight to halve its cost (using floor division, i.e., ⌊x/2⌋).
• You can use the coupon only once and on any flight in your route.

The task is to determine the minimum possible total flight cost considering the optimal place to use the coupon.

---

💡 Proposed Approach

We'll use Dijkstra’s algorithm with a state-space expansion approach:

• Each node can be reached in two states:
  1. Without using the discount yet
  2. After using the discount

Algorithm Steps:

1. Build an adjacency list for all directed edges (a, b, c).
2. Maintain a dist[node][state] array where:
   • state = 0: Discount not used
   • state = 1: Discount already used
3. Use a priority queue (min-heap) for Dijkstra traversal:
   • For each edge (u, v, w):
     • If discount not used yet, we have two choices:
       • Travel normally: dist[v][0] = dist[u][0] + w
       • Use discount now: dist[v][1] = dist[u][0] + w // 2
     • If discount already used:
       • Only travel normally: dist[v][1] = dist[u][1] + w
4. Continue until all reachable nodes are processed.
5. The answer will be dist[n][1], i.e., the minimum distance to city n with discount used optimally.

Time Complexity:

• O((n + m) log n) using Dijkstra’s algorithm (each edge processed twice due to two states).

Space Complexity:

• O(n + m) for adjacency list + O(2n) for distance states.

---

📝 Implementation Notes

• Requires fast I/O
• Needs modular arithmetic
• Large input constraints
• Edge cases to consider

---

🏷️ Labels

• hacktoberfest
• good first issue
• help wanted

---

👤 Assignee

• I would like to work on this issue
• I'm available for guidance/review

---

📎 Additional Context

[vingoel26]

@ks-iitjmu please assign this to me