Finding intersting path in a graph

Question

There is a question in a contest but it doesn't have any answer. I solve it but I get time limit for most of test case. Is it possible to improve my code or give a better approach?

Question

There is a directed graph with vertices \$1,...,n\$ and each vertex has a label which is \$a_i\$ (a number not character). we start walk and write label for each vertex we see in path (we can use vertices and edges more than one time) for example if we start from vertex \$v\$ and go to vertex \$u\$ then string of path is \$a_va_u\$. (if \$a_v=23\$ and \$a_u=456\$ then string of path is \$23456\$) we want to find strings of length \$k\$ and between different way of find that, choose one that produce maximum string of path (larger number) and print it.

Input

In the first line numbers n,m,k are given denoting the number of vertices, edges and length of string path that we want. Next line contains n integers one after another, i-th integer is equal to \$a_i\$​. (the number written on vertex i) Afterwards m lines each consisting of two integers u, v are given showing edge \$u \rightarrow v\$ exists in the graph.
\$1 \le v, u \le n\$
\$n, m, k \le 1000\$
\$1 \le a_i \le 100000\$
the graph can contain loop or multiple edges.

Output

In the only line of output display the k digit number that is maximized. Display −1 if no answer exists!

Sample input

5 4 3
4 12 3 1 1
1 2
2 3
1 4
4 5

Sample output

412

My Solution

In my solution because we can traverse each edges and vertices more than one time, so I don't use something like visited array. I use deep first search to traverse all vertices and because we solve some problems more than one time, I use dynamic programming approach (to-down with memoization) to solve it faster however I get time limit. I Think my solution is right and I have time problem but maybe you find some implementation problem. (I hope that is true)

#include <iostream>
#include <vector>

using namespace std;

int *value;
int *size;
int **valueC;
vector<int> *edges;
int k;

int length(int n);
int concat(const int &n1, const int &n2);
int dfs(int i, int reminder);

int length(int n) {
    int s = 0;
    do {
        n /= 10;
        s++;
    } while (n > 0);
    return s;
}

int concat(const int &n1, const int &n2) {
    int times = 1;
    while (times <= n2)
        times *= 10;
    return n1 * times + n2;
}


int dfs(int i, int reminder) {
    if (valueC[i][reminder] != -1)
        return valueC[i][reminder];
    int q = -1;
    for (int j : edges[i]) {
        int temp = -2;
        if (reminder - size[j] == 0)
            temp = value[j];
        else if (reminder - size[j] > 0)
            temp = dfs(j, reminder - size[j]);
        if (temp > q)
            q = temp;
    }
    if (q == -1)
        valueC[i][reminder] = -2;
    else
        valueC[i][reminder] = concat(value[i], q);
    return valueC[i][reminder];
}

int main() {
    int n, m;
    cin >> n >> m >> k;
    if (k == 0) {
        cout << -1;
        return 0;
    }
    value = new int[n];
    size = new int[n];
    valueC = new int *[n];
    for (int i = 0; i < n; ++i) {
        valueC[i] = new int[k];
        for (int j = 0; j < k; ++j) {
            valueC[i][j] = -1;
        }
    }
    for (int i = 0; i < n; ++i) {
        cin >> value[i];
        size[i] = length(value[i]);
    }
    edges = new vector<int>[n];
    for (int j = 0; j < m; ++j) {
        int s, e;
        cin >> s >> e;
        s--;
        e--;
        edges[s].push_back(e);
    }

    int maximum = 0;
    for (int i = 0; i < n; ++i) {
        int temp = dfs(i, k - size[i]);
        if (temp > maximum)
            maximum = temp;
    }

    if (maximum != 0)
        cout << maximum;
    else
        cout << -1;
    return 0;
}

Update 1

I remove one more space that is used as mentioned. about edges I use vector<int>[n] because I have n vertices and for each vertex I use a vector<int> to know that is connected to which vertices. about concat and length, I use int and I don't worry because the restriction on the question say that my numbers are at most 100000 and that is enough and both function work without overflow.

Answer 1

Your code is fairly readable, which is good. I see a few things that could be improved, though.

Bugs

In main() you are allocating n + 1 elements and then iterating from 1 to n. C-based languages use 0-based arrays, so always allocating 1 extra and ignoring index 0 is likely to introduce bugs as future programmers (including a future you) assume that an array goes from 0 to n - 1. I know this because I've had to maintain such code and it was a source of bugs. It's also wasteful because every array has an extra element in it that's never used.

That said you have a current bug in this code:

edges = new vector<int>[n + 1];
for (int j = 0; j < m; ++j) {
    int s, e;
    cin >> s >> e;
    edges[s].push_back(e);
}

The instructions say there are m edges. You've allocated n + 1 edges which may be too many or too few. If it's too few, then you will overwrite memory and mess up your heap.

Simplify

Your length() function runs a loop when it doesn't need to. You can do it like this:

int length(const int n)
{
    if ((n == 0) || (n == 1))
    {
        return 1;
    }
    
    return ceil(log10(n));
}

Likewise, your concat() function could remove the loop with a call to log10() and a call to pow().

Whether either of these is faster than what you've written or not probably depends on the number of decimal digits in the vertices. I recommend trying it and profiling to see which is faster.

The end of your dfs() function is written very confusingly and is redundant. I would simplify it by doing this instead:

if (q == -1)
{
    valueC[i][reminder] = -2;
}
else
{
    valueC[i][reminder] = concat(value[i], q);
}
return valueC[i][reminder];