# 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.
```
# SolutionTo 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 = 1for 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 += 1print(r.recvall())```