Submission #2010912
Source Code Expand
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> P2;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
int N, M, S, T;
vector<P> G[25252];
int dist[25252];
map<int, P> nxt[25252];
map<int, P> ext[25252];
map<int, int> D[25252];
inline int get(int x, int y) {
if (D[x].find(y) == D[x].end()) return INF;
return D[x][y];
}
bool f(int X) {
rep(i, N) D[i].clear();
priority_queue<P2> q;
q.push(P2(0, P(S, -1)));
D[S][-1] = 0;
while (!q.empty()) {
int r = q.top()._1, x = q.top()._2._1, e = q.top()._2._2;
q.pop();
if (get(x, e) < r) continue;
if (e == -1) {
// in
for (P2 p : nxt[x]) {
int ne = p._1;
if (get(x, ne) > r) {
D[x][ne] = r;
q.push(P2(r, P(x, ne)));
}
}
}
else {
int to = nxt[x][e]._1, len = nxt[x][e]._2;
if (to != -1 && get(to, e) > r+len) {
D[to][e] = r+len;
q.push(P2(r+len, P(to, e)));
}
// out
int over = r+dist[ext[x][e]._1]+ext[x][e]._2;
if (over <= X && get(x, -1) > r) {
D[x][-1] = r;
q.push(P2(r, P(x, -1)));
}
}
}
return get(T, -1) <= X;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> N >> M >> S >> T;
rep(e, M) {
int l;
cin >> l;
vector<int> s(l), w(l-1);
rep(i, l) cin >> s[i];
rep(i, l-1) cin >> w[i];
rep(i, l-1) {
G[s[i]].pb(P(s[i+1], w[i]));
G[s[i+1]].pb(P(s[i], w[i]));
}
rep(k, 2) {
rep(i, l-1) nxt[s[i]][e*2+k] = P(s[i+1], w[i]);
nxt[s.back()][e*2+k] = P(-1, -1);
int cost = 0;
for (int i=l-1; i>=0; i--) {
if (i < w.size()) cost += w[i];
ext[s[i]][e*2+k] = P(s.back(), cost);
}
reverse(all(s));
reverse(all(w));
}
}
rep(i, N) dist[i] = INF;
priority_queue<P> q;
q.push(P(0, T));
dist[T] = 0;
while (!q.empty()) {
int r = q.top()._1, x = q.top()._2;
q.pop();
if (dist[x] < r) continue;
for (P p : G[x]) {
int t = p._1, len = p._2;
if (dist[t] > r+len) {
dist[t] = r+len;
q.push(P(dist[t], t));
}
}
}
int lo = 0, hi = INF;
while (hi - lo > 1) {
int mid = (0LL + lo + hi) / 2;
if (f(mid)) hi = mid;
else lo = mid;
}
cout << hi << "\n";
return 0;
}
Submission Info
Submission Time |
|
Task |
C - メンテナンス明け |
User |
funcsr |
Language |
C++14 (GCC 5.4.1) |
Score |
50 |
Code Size |
2910 Byte |
Status |
TLE |
Exec Time |
2661 ms |
Memory |
20772 KB |
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Score / Max Score |
50 / 50 |
0 / 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 |
TLE |
2661 ms |
18688 KB |
large/20_large-01 |
TLE |
2657 ms |
20772 KB |
large/20_large-02 |
TLE |
2656 ms |
20736 KB |
large/20_large-03 |
TLE |
2657 ms |
18560 KB |
large/20_large-04 |
TLE |
2657 ms |
18688 KB |
large/31_max_large |
TLE |
2657 ms |
15420 KB |
small/00_sample00 |
AC |
3 ms |
4480 KB |
small/00_sample01 |
AC |
3 ms |
4480 KB |
small/00_sample02 |
AC |
3 ms |
4480 KB |
small/10_small-0000 |
AC |
664 ms |
4736 KB |
small/10_small-0001 |
AC |
669 ms |
4736 KB |
small/10_small-0002 |
AC |
217 ms |
4736 KB |
small/10_small-0003 |
AC |
371 ms |
4736 KB |
small/10_small-0004 |
AC |
628 ms |
4736 KB |
small/10_small-0005 |
AC |
411 ms |
4736 KB |
small/10_small-0006 |
AC |
569 ms |
4736 KB |
small/10_small-0007 |
AC |
538 ms |
4736 KB |
small/10_small-0008 |
AC |
581 ms |
4736 KB |
small/10_small-0009 |
AC |
381 ms |
4736 KB |
small/10_small-0010 |
AC |
321 ms |
4608 KB |
small/10_small-0011 |
AC |
745 ms |
4736 KB |
small/10_small-0012 |
AC |
454 ms |
4736 KB |
small/10_small-0013 |
AC |
425 ms |
4736 KB |
small/10_small-0014 |
AC |
532 ms |
4736 KB |
small/10_small-0015 |
AC |
606 ms |
4736 KB |
small/10_small-0016 |
AC |
356 ms |
4608 KB |
small/10_small-0017 |
AC |
511 ms |
4736 KB |
small/10_small-0018 |
AC |
510 ms |
4736 KB |
small/10_small-0019 |
AC |
299 ms |
4608 KB |
small/30_max_small |
AC |
62 ms |
4608 KB |
small/40_simple_0000 |
AC |
3 ms |
4480 KB |
small/40_simple_0001 |
AC |
3 ms |
4480 KB |
small/40_simple_0002 |
AC |
3 ms |
4480 KB |
small/40_simple_0003 |
AC |
3 ms |
4480 KB |
small/40_simple_0004 |
AC |
3 ms |
4480 KB |
small/40_simple_0005 |
AC |
3 ms |
4480 KB |
small/40_simple_0006 |
AC |
3 ms |
4480 KB |
small/40_simple_0007 |
AC |
3 ms |
4480 KB |
small/40_simple_0008 |
AC |
3 ms |
4480 KB |
small/40_simple_0009 |
AC |
3 ms |
4480 KB |
small/40_simple_0010 |
AC |
3 ms |
4480 KB |
small/40_simple_0011 |
AC |
3 ms |
4480 KB |
small/40_simple_0012 |
AC |
3 ms |
4480 KB |
small/40_simple_0013 |
AC |
3 ms |
4480 KB |
small/40_simple_0014 |
AC |
3 ms |
4480 KB |
small/40_simple_0015 |
AC |
3 ms |
4480 KB |
small/40_simple_0016 |
AC |
3 ms |
4480 KB |
small/40_simple_0017 |
AC |
3 ms |
4480 KB |
small/40_simple_0018 |
AC |
3 ms |
4480 KB |
small/40_simple_0019 |
AC |
3 ms |
4480 KB |
small/90_dijkstra_killer_00 |
AC |
3 ms |
4480 KB |
small/90_dijkstra_killer_01 |
AC |
3 ms |
4480 KB |
small/91_tayama_killer_00 |
AC |
3 ms |
4480 KB |
small/91_tayama_killer_01 |
AC |
3 ms |
4480 KB |
small/91_tayama_killer_02 |
AC |
3 ms |
4480 KB |
small/91_tayama_killer_03 |
AC |
3 ms |
4480 KB |
small/91_tayama_killer_04 |
AC |
3 ms |
4480 KB |
small/91_tayama_killer_05 |
AC |
3 ms |
4480 KB |