# Problem Statement
```
+++ 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.

```

# Solution
To solve this problem we model each door being a vertex and each path being an edge on a graph. Now our problem is to find the shortest path between `C` and `E` and this is a classical problem with an already existing algorithm (we call it Dijkstra's algorithm for shortest paths in my country). The implementation can be found on my [ICPC notebook](https://github.com/chinchila/ICPC/blob/master/code/graphs/dijkstra.cpp). But our problem is a bit harder, instead relaxing the vertex just like on dijkstra, we have to relax it a little bit different, calling the time `cost[i]` of each door i, when dijkstra is processing the edge uv, we have to treat the edge weight `w[uv]` as the first multiple of `cost[i]` greater than or equal `w[uv]`.

## implementation
```
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f

int n, m, c, e;
vector<pair<int, ll> > g[1000010];
int cost[1000010];

vector<ll> dk( int start ) {
vector<ll> dist( n + 5, INF );
priority_queue<pair<ll, int> > q;
q.push( { dist[start] = 0, start } );
while( !q.empty() ) {
int u = q.top().second;
ll d = -q.top().first; q.pop();
for( pair<int, ll> pv : g[u] ) {
int v = pv.first, w = pv.second;
ll k = dist[u] + w;
ll nd = cost[v]*((k+cost[v]-1)/cost[v]);
if( nd < dist[v] )
q.push( { -( dist[v] = nd ), v } );
}
}
return dist;
}

int main(int argc, char* argv[]) {
scanf("%d%d", &n, &m);
for( int i = 1 ; i <= n ; ++i ) {
scanf("%d", cost+i);
}
for( int i = 0 ; i < m ; ++i ) {
int u, v;
ll w;
scanf("%d%d%lld", &u, &v, &w);
g[u].push_back({v, w});
g[v].push_back({u, w});
}
scanf("%d%d", &c, &e);
auto l = dk( c );
printf("%lld\n", l[e] );
return 0;
}

```

Compile it with g++ file.cpp

## Autosend tests script
```
from pwn import *
from subprocess import Popen, PIPE, STDOUT

r = remote("142.93.113.55", 31085)
r.recvuntil("runaway:")
r.sendline("start")
r.recvuntil("is:")
r.sendline("11")
passed = 1
for i in range(50):
print("Passou: " + str(passed))
k = r.recvuntil("is:")
lines = k.split("\n")[3:-2]
p = Popen(['./a.out'], stdout=PIPE, stdin=PIPE, stderr=STDOUT)
inf = '\n'.join(lines)
out = p.communicate(input=inf)[0][:-1]
r.sendline(out)
passed += 1
print(r.recvall())
```