**Tags:** graphs ppc

Rating:

# 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())

```