bogdan e tare

#include <fstream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define DIM 1030
#define DIMM 16005
#define DIMT 130
#define INF 2000000000
#define pint vector< pair<int, int> >::iterator
#define infile "patrol.in"
#define outfile "patrol.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

struct comp {

    bool operator()(pair< pair<int, int>, int> a, pair< pair<int, int>, int> b) {
        return a.second > b.second;
    }

};

priority_queue < pair< pair<int, int>, int>, vector< pair< pair<int, int>, int> >, comp > H;

int n, m, p;

int cost[DIM], polizei[530][10], dp[DIM][DIMT], ok[DIM][DIMT];

bool okNode[DIM][DIMT], okEdge[DIMM][DIMT];

vector< pair<int, int> > L[DIM];

map< pair<int, int>, int> muchii;

int main() {

    f >> n >> m >> p;

    for (int i = 1; i <= n; ++i)
        f >> cost[i];

    int nrMuchii = 0;

    for (int i = 1; i <= m; ++i) {

        int x, y;

        f >> x >> y;

        muchii[make_pair(x, y)] = ++nrMuchii;
        L[x].push_back(make_pair(y, nrMuchii));

        muchii[make_pair(y, x)] = ++nrMuchii;
        L[y].push_back(make_pair(x, nrMuchii));

    }

    int cmmmc = 1;

    for (int i = 1; i <= p; ++i) {

        f >> polizei[i][0];

        for (int j = 1; j <= polizei[i][0]; ++j)
            f >> polizei[i][j];

        int a = cmmmc, b = 2 * (polizei[i][0] - 1);

        cmmmc *= 2 * (polizei[i][0] - 1);

        while (b) {

            int r = a%b;
            a = b;
            b = r;

        }

        cmmmc /= a;

    }

    for (int i = 1; i <= p; ++i) {

        for (int step = 0, j = 1, dir = 1; step < cmmmc; ++step) {

            if (j == polizei[i][0] + 1)
                dir = -1, j = polizei[i][0] - 1;

            if (j == 0)
                dir = 1, j = 2;

            okNode[polizei[i][j]][step] = 1;

            int nextj = j + dir;

            if (nextj == polizei[i][0] + 1)
                nextj = polizei[i][0] - 1;
            else
                if (nextj == 0)
                    nextj = 2;

            int edge = muchii[make_pair(polizei[i][nextj], polizei[i][j])];

            okEdge[edge][step] = 1;

            j += dir;

        }

    }

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < cmmmc; ++j)
            dp[i][j] = INF;

    H.push(make_pair(make_pair(1, 0), cost[1]));

    dp[1][0] = cost[1];

    while (!H.empty()) {

        while (!H.empty() && ok[H.top().first.first][H.top().first.second])
            H.pop();

        if (H.empty())
            break;

        int node = H.top().first.first;
        int crtTime = H.top().first.second;

        dp[node][crtTime] = H.top().second;

        ok[node][crtTime] = 1;

        int nextTime = crtTime + 1;

        if (nextTime >= cmmmc)
            nextTime -= cmmmc;

        for (pint it = L[node].begin(); it != L[node].end(); ++it) {

            if (okNode[it->first][nextTime] || okEdge[it->second][crtTime])
                continue;

            if (dp[it->first][nextTime] > dp[node][crtTime] + cost[it->first])
                H.push(make_pair(make_pair(it->first, nextTime), dp[node][crtTime] + cost[it->first]));

        }

    }

    int sol = INF;

    for (int i = 0; i < cmmmc; ++i)
        sol = std::min(sol, dp[n][i]);

    g << sol;

    return 0;
}