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
Submission Time |
|
Task |
C - メンテナンス明け |
User |
takapt |
Language |
C++11 (GCC 4.9.2) |
Score |
100 |
Code Size |
7433 Byte |
Status |
AC |
Exec Time |
326 ms |
Memory |
3572 KB |
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Score / Max Score |
50 / 50 |
50 / 50 |
Status |
|
|
Set Name |
Test Cases |
Subtask1 |
small/00_sample00, small/00_sample01, small/00_sample02, small/10_small-0000, small/10_small-0001, small/10_small-0002, small/10_small-0003, small/10_small-0004, small/10_small-0005, small/10_small-0006, small/10_small-0007, small/10_small-0008, small/10_small-0009, small/10_small-0010, small/10_small-0011, small/10_small-0012, small/10_small-0013, small/10_small-0014, small/10_small-0015, small/10_small-0016, small/10_small-0017, small/10_small-0018, small/10_small-0019, small/30_max_small, small/40_simple_0000, small/40_simple_0001, small/40_simple_0002, small/40_simple_0003, small/40_simple_0004, small/40_simple_0005, small/40_simple_0006, small/40_simple_0007, small/40_simple_0008, small/40_simple_0009, small/40_simple_0010, small/40_simple_0011, small/40_simple_0012, small/40_simple_0013, small/40_simple_0014, small/40_simple_0015, small/40_simple_0016, small/40_simple_0017, small/40_simple_0018, small/40_simple_0019, small/90_dijkstra_killer_00, small/90_dijkstra_killer_01, small/91_tayama_killer_00, small/91_tayama_killer_01, small/91_tayama_killer_02, small/91_tayama_killer_03, small/91_tayama_killer_04, small/91_tayama_killer_05 |
Subtask2 |
large/20_large-00, large/20_large-01, large/20_large-02, large/20_large-03, large/20_large-04, large/31_max_large |
Case Name |
Status |
Exec Time |
Memory |
large/20_large-00 |
AC |
273 ms |
3468 KB |
large/20_large-01 |
AC |
276 ms |
3528 KB |
large/20_large-02 |
AC |
326 ms |
3540 KB |
large/20_large-03 |
AC |
274 ms |
3572 KB |
large/20_large-04 |
AC |
300 ms |
3572 KB |
large/31_max_large |
AC |
57 ms |
2600 KB |
small/00_sample00 |
AC |
26 ms |
812 KB |
small/00_sample01 |
AC |
25 ms |
808 KB |
small/00_sample02 |
AC |
24 ms |
800 KB |
small/10_small-0000 |
AC |
30 ms |
900 KB |
small/10_small-0001 |
AC |
27 ms |
808 KB |
small/10_small-0002 |
AC |
26 ms |
800 KB |
small/10_small-0003 |
AC |
26 ms |
804 KB |
small/10_small-0004 |
AC |
25 ms |
796 KB |
small/10_small-0005 |
AC |
26 ms |
732 KB |
small/10_small-0006 |
AC |
26 ms |
800 KB |
small/10_small-0007 |
AC |
27 ms |
804 KB |
small/10_small-0008 |
AC |
27 ms |
808 KB |
small/10_small-0009 |
AC |
30 ms |
916 KB |
small/10_small-0010 |
AC |
25 ms |
928 KB |
small/10_small-0011 |
AC |
25 ms |
924 KB |
small/10_small-0012 |
AC |
27 ms |
812 KB |
small/10_small-0013 |
AC |
27 ms |
808 KB |
small/10_small-0014 |
AC |
26 ms |
800 KB |
small/10_small-0015 |
AC |
25 ms |
924 KB |
small/10_small-0016 |
AC |
25 ms |
800 KB |
small/10_small-0017 |
AC |
26 ms |
800 KB |
small/10_small-0018 |
AC |
26 ms |
804 KB |
small/10_small-0019 |
AC |
26 ms |
800 KB |
small/30_max_small |
AC |
27 ms |
920 KB |
small/40_simple_0000 |
AC |
25 ms |
800 KB |
small/40_simple_0001 |
AC |
27 ms |
924 KB |
small/40_simple_0002 |
AC |
27 ms |
924 KB |
small/40_simple_0003 |
AC |
27 ms |
804 KB |
small/40_simple_0004 |
AC |
27 ms |
924 KB |
small/40_simple_0005 |
AC |
25 ms |
800 KB |
small/40_simple_0006 |
AC |
25 ms |
924 KB |
small/40_simple_0007 |
AC |
27 ms |
924 KB |
small/40_simple_0008 |
AC |
27 ms |
920 KB |
small/40_simple_0009 |
AC |
26 ms |
924 KB |
small/40_simple_0010 |
AC |
25 ms |
924 KB |
small/40_simple_0011 |
AC |
25 ms |
924 KB |
small/40_simple_0012 |
AC |
27 ms |
800 KB |
small/40_simple_0013 |
AC |
26 ms |
788 KB |
small/40_simple_0014 |
AC |
25 ms |
808 KB |
small/40_simple_0015 |
AC |
25 ms |
812 KB |
small/40_simple_0016 |
AC |
25 ms |
920 KB |
small/40_simple_0017 |
AC |
25 ms |
920 KB |
small/40_simple_0018 |
AC |
25 ms |
928 KB |
small/40_simple_0019 |
AC |
25 ms |
916 KB |
small/90_dijkstra_killer_00 |
AC |
25 ms |
804 KB |
small/90_dijkstra_killer_01 |
AC |
26 ms |
800 KB |
small/91_tayama_killer_00 |
AC |
25 ms |
912 KB |
small/91_tayama_killer_01 |
AC |
26 ms |
796 KB |
small/91_tayama_killer_02 |
AC |
25 ms |
804 KB |
small/91_tayama_killer_03 |
AC |
26 ms |
808 KB |
small/91_tayama_killer_04 |
AC |
25 ms |
920 KB |
small/91_tayama_killer_05 |
AC |
25 ms |
804 KB |