##  Problem Description
```                +++     Fireshell CTF - DUNGEON ESCAPE     +++
 [+] After being caught committing crimes, you were locked up in a really strange      dungeon. You found out that the jailer is corrupt and after negotiating     with him, he showed to you a map with all the paths and the necessary time     to cross each one, and explained to you how the dungeon works. In some     parts of the dungeon, there are some doors that only open periodically. The     map looks something like this:
                4              +-+      1        +----------------------+3+-------------+       +-+                     +-+             |       |C|                              2     +++     4       +++                  +-----------------+7+--------------------+        |           3      +-+                +-+                    |        +------------------+4|        12                            +++                           +-+--------------------------------------+E|                                                                    +-+
 [+] All doors start at time zero together and if a door has time equals to 3,     this door will open only at times 0, 3, 6, 9, ... So if you reach a door     before it is open, you will need to wait until the door is open.
 [+] So, with a map you organized the infos like the following: first it will be      the number of doors and the number of paths. Second it will be a list with     the time of all doors. After that each line will contains a path with the     time needed to walk this path. For the last it will be the position of your     cell (C) and the postion where it is the exit (E).  [+] The jailer said that if you find out the minimum time from your cell to the      exit, he will set you free. In the example, the minimum time is 11.```
### Sample Input
```5 61 8 3 7 11 2 31 3 42 4 23 4 12 5 124 5 41 5```
### Sample Output
```11```
## Solution
We can interpret it as a graph problem: each door is a vertex and each path is an undirected edge with a weight assigned. We are to find the shortest path between the nodes $C$ and $E$.
Since we want to calculate the shortest path, [Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) seems like a good idea. The only thing now is to handle the doors' open times. If we arrive at a door with open interval $t$ at time $x$, we have to wait until the time reaches a multiple of $t$ that is $\geq x$, which is $\left\lceil \frac{x}{t} \right\rceil t$. Therefore when arriving at a new node, we should set its distance to $\left\lceil \frac{x}{t} \right\rceil t$ instead of $x$ (as in the usual Dijkstra's).
### Code
Here is a C++ implementation that passes all challenges. The code is not well-optimized for size or speed for the sake of readability.
```c++#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int n, m;vector<int> intervals;vector<vector<pii>> edges;
int get_open_time(int time, int open_time) {    if(time == 0) return 0;    return ((time - 1) / open_time + 1) * open_time;}
int solve(int start_node, int end_node) {    priority_queue<pii, vector<pii>, greater<pii>> Q;    vector<bool> visited(n + 1);
    Q.emplace(0, start_node);    while(Q.top().second != end_node) {        int dist = Q.top().first, node = Q.top().second;        Q.pop();        if(!visited[node])            for(pii &edge : edges[node])                Q.emplace(get_open_time(dist + edge.second, intervals[edge.first]), edge.first);        visited[node] = true;    }    return Q.top().first;}
int main() {    cin >> n >> m;
    intervals.resize(n + 1);    for(int i = 1; i <= n; i++)        cin >> intervals[i];
    edges.resize(n + 1);    for(int i = 1; i <= m; i++) {        int u, v, w;        cin >> u >> v >> w;        edges[u].emplace_back(v, w);        edges[v].emplace_back(u, w);    }
    int start_node, end_node;    cin >> start_node >> end_node;    cout << solve(start_node, end_node) << '\n';
    return 0;}```
### Interaction Script (credit: lys0829)
This task requires an interaction with the server. Here is a python script that works with the above solution.
```pyfrom pwn import *
r = remote('142.93.113.55', 31085)r.sendlineafter('runaway: ', 'start')
for chal in range(1, 51):    try:        # assume the compiled file is ./main        sol = process('./main', level='error')
        print(f'Running on test {chal}')        r.recvuntil(f'Challenge {chal}:')        test = r.recvuntil('The answer is: ')
        sol.send(test)        r.send(sol.recvline())        result = r.recvline()        if 'Correct!' not in result.decode():            print(f'Wrong answer on test {chal}')            exit(1)
    except Exception:        print(f'Runtime error on test {chal}')        exit(2)
print(r.recvall().decode())# congratulations, you now have the flag!```
