//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;

const int maxn = 31;
vector <pair<int, ii>> g[maxn][maxn];
int d[maxn][maxn];

bool _sort(ii a, ii b) {
    if (d[a.fi][a.se] != d[b.fi][b.se]) re d[a.fi][a.se] < d[b.fi][b.se];
    re a < b;
}

set <ii, bool (*) (ii, ii)> s(_sort);

void read (int a, int b) {
    int k, x, w;
    cin >> k;
    fo(i, k) {
        cin >> x;
        while (x != 0) {
            cin >> w ;
            g[a][x - 1].pb(mp(b, mp(i, w)));
            cin >> x;
        }
    }
}

void dejkstra() {
    fo(i, maxn) fo(j, maxn) d[i][j] = (int) 1e9;
    d[0][0] = 0;
    int x, y, a, b, w;
    s.insert(mp(0, 0));
    while (!s.empty()) {
        x = (*s.begin()).fi, y = (*s.begin()).se;
        s.erase(s.begin());
        for (auto &j : g[x][y]) {
            a = j.fi, b = j.se.fi, w = j.se.se;
            if (d[a][b] > d[x][y] + w) {
                s.erase(mp(a, b));
                d[a][b] = d[x][y] + w;
                s.insert(mp(a, b));
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    string str;
    for (int i = 1; i <= n; ++i) {
        read (i - 1, i);
        if (i < n) cin >> str;
    }
    dejkstra();
    int ans = (int) 1e9;
    fo(i, maxn) ans = min(ans, d[n][i]);
    cout << ans << endl;
}

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
    int n;
    cin >> n; // quantity of levels in Ivans map
    int cs[35][35][35];
    vector<int> v[35][35];
    int inLevel[35];
    for(int i = 1; i <= n; ++i)
    {
        int k;
        cin >> k;
        inLevel[i] = k;
        for(int j = 1; j <= k; ++j)
        {
            while(true)
            {
                int a, b;
                cin >> a;
                if(a == 0)
                {
                    break;
                }
                cin >> b;
                v[i][j].push_back(a); /// on i-th level to planet "j" we can come from planet "a" in i-1 - th level
                cs[i][j][a] = b;  /// on i-1-th level planet "a" pay b$ for going to planet "j" in i-th - level
            }
        }
        if(i == n)
            break;
        char x;
        cin >> x;
    }

    int dist[35][35];
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= inLevel[i]; ++j)
        {
            dist[i][j] = 10010010;
        }
    }

    dist[0][1] = 0;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= inLevel[i]; ++j)
        {
            for(int k = 0; k < v[i][j].size(); ++k)
            {
                int pl = v[i][j][k];
                if(dist[i][j] > dist[i-1][pl] + cs[i][j][pl])
                {
                    dist[i][j] = dist[i-1][pl] + cs[i][j][pl];
                }
            }
        }
    }

    int mn = 10010020;
    for(int i = 1; i <= inLevel[n]; ++i)
    {
        mn = min(mn, dist[n][i]);
    }

    cout << mn;
}
sorry for my terrible english

Edited by author 11.11.2019 04:02