Submission #618038

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <bitset>

using namespace std;

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
template <typename T> void print_container(ostream& os, const T& c) { const char* _s = " "; if (!c.empty()) { __typeof__(c.begin()) last = --c.end(); foreach (it, c) { os << *it; if (it != last) os << _s; } } }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const set<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const multiset<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const deque<T>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; }

template <typename T> void print(T a, int n, const string& split = " ") { for (int i = 0; i < n; i++) { cout << a[i]; if (i + 1 != n) cout << split; } cout << endl; }
template <typename T> void print2d(T a, int w, int h, int width = -1, int br = 0) { for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (width != -1) cout.width(width); cout << a[i][j] << ' '; } cout << endl; } while (br--) cout << endl; }
template <typename T> void input(T& a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }
#define dump(v) (cout << #v << ": " << v << endl)

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define erep(i, n) for (int i = 0; i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define clr(a, x) memset(a, x, sizeof(a))
#define sz(a) ((int)(a).size())
#define mp(a, b) make_pair(a, b)
#define ten(n) ((long long)(1e##n))

template <typename T, typename U> void upmin(T& a, const U& b) { a = min<T>(a, b); }
template <typename T, typename U> void upmax(T& a, const U& b) { a = max<T>(a, b); }
template <typename T> void uniq(T& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }
template <class T> string to_s(const T& a) { ostringstream os; os << a; return os.str(); }
template <class T> T to_T(const string& s) { istringstream is(s); T res; is >> res; return res; }
void fast_io() { cin.tie(0); ios::sync_with_stdio(false); }
bool in_rect(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }

typedef long long ll;
typedef pair<int, int> pint;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };


int main()
{
    fast_io();

    int n, m, src, dst;
    cin >> n >> m >> src >> dst;
    vector<vector<pint>> g;
    vector<vector<int>> l;
    vector<vector<int>> w;
    vector<vector<int>> cum_w;
    g.resize(n);
    l.resize(m);
    w.resize(m);
    cum_w.resize(m);
    rep(i, m)
    {
        int t;
        cin >> t;
        l[i].resize(t);
        w[i].resize(t - 1);
        input(l[i], t);
        input(w[i], t - 1);

        rep(index, t)
        {
            g[l[i][index]].push_back(pint(i, index));
        }
    }
    rep(i, m)
    {
        cum_w[i].resize(w[i].size() + 1);
        cum_w[i][0] = 0;
        rep(j, w[i].size())
            cum_w[i][j + 1] = cum_w[i][j] + w[i][j];
    }

    int min_dist[114514];
    {
        fill_n(min_dist, n, ten(9));
        priority_queue<pint, vector<pint>, greater<pint>> q;
        min_dist[dst] = 0;
        q.push(pint(0, dst));
        while (!q.empty())
        {
            int cur, cost;
            tie(cost, cur) = q.top();
            q.pop();

            if (cost > min_dist[cur])
                continue;

            for (auto& e : g[cur])
            {
                int line_i, i;
                tie(line_i, i) = e;

                const auto& line = l[line_i];
                const auto& ww = w[line_i];

                if (i > 0)
                {
                    int next = line[i - 1];
                    int ncost = cost + ww[i - 1];
                    if (ncost < min_dist[next])
                    {
                        min_dist[next] = ncost;
                        q.push(pint(ncost, next));
                    }
                }
                if (i + 1 < line.size())
                {
                    int next = line[i + 1];
                    int ncost = cost + ww[i];
                    if (ncost < min_dist[next])
                    {
                        min_dist[next] = ncost;
                        q.push(pint(ncost, next));
                    }
                }
            }
        }
    }

    auto check = [&](int max_time)
    {
        int dp[114514];
        fill_n(dp, n, max_time + 1);

        priority_queue<pint, vector<pint>, greater<pint>> q;
        dp[src] = 0;
        q.push(pint(0, src));
        while (!q.empty())
        {
            int cur, cost;
            tie(cost, cur) = q.top();
            q.pop();

            if (cost > dp[cur])
                continue;

            for (auto& e : g[cur])
            {
                int line_i, i;
                tie(line_i, i) = e;

                const auto& line = l[line_i];
                const auto& ww = w[line_i];
                const auto& cum = cum_w[line_i];

                if (i > 0)
                {
                    int through = cost + cum[i] + min_dist[line[0]];
                    if (through <= max_time)
                    {
                        int next = line[i - 1];
                        int ncost = cost + ww[i - 1];
                        if (ncost < dp[next])
                        {
                            dp[next] = ncost;
                            q.push(pint(ncost, next));
                        }
                    }
                }
                if (i + 1 < line.size())
                {
                    int through = cost + (cum.back() - cum[i]) + min_dist[line.back()];
                    if (through <= max_time)
                    {
                        int next = line[i + 1];
                        int ncost = cost + ww[i];
                        if (ncost < dp[next])
                        {
                            dp[next] = ncost;
                            q.push(pint(ncost, next));
                        }
                    }
                }
            }
        }

        return dp[dst] <= max_time;
    };

    int low = -1, high = ten(9);
    while (high - low > 1)
    {
        int mid = (low + high) / 2;
        if (check(mid))
            high = mid;
        else
            low = mid;
    }
    cout << high << endl;
}

Submission Info

Judge Result