Submission #1027037
Source Code Expand
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <queue> using namespace std; #define INF (1LL<<60) #define MAX_B 200000 typedef pair<int, int> P; typedef pair<long long, P> P2; int N, M, S, D; vector<P2> edges[253]; long long d[253][MAX_B+1]; int main() { cin >> N >> M >> S >> D; if (N >= 253) return 1; for (int k=0; k<M; k++) { int L; cin >> L; int s[L], w[L]; for (int i=0; i<L; i++) cin >> s[i]; for (int i=0; i<L-1; i++) cin >> w[i]; int t = 0, sum = 0; for (int i=0; i<L-1; i++) sum += w[i]; for (int i=0, g=sum; i<L; i++) { int l = 0; for (int j=i+1, g2=g; j<L; j++) { g2 -= w[j-1]; l += w[j-1]; edges[s[i]].push_back(P2(s[j], P(l, g2))); } g -= w[i]; } for (int i=L-1, g=sum; i>=0; i--) { int l = 0; for (int j=i-1, g2=g; j>=0; j--) { g2 -= w[j]; l += w[j]; edges[s[i]].push_back(P2(s[j], P(l, g2))); } g -= w[i-1]; } } for (int i=0; i<N; i++) { for (int j=0; j<MAX_B; j++) { d[i][j] = INF; } } priority_queue< P2, vector<P2>, greater<P2> > q; d[S][0] = 0; q.push(P2(0, P(S, 0))); long long ans = INF; while (!q.empty()) { int r = q.top().first, s = q.top().second.first, b = q.top().second.second; q.pop(); if (d[s][b] > r) continue; for (P2 p : edges[s]) { int t = p.first; int r1 = p.second.first, r2 = p.second.second; int w = max(b, r2*2); if (d[t][w] > d[s][b] + r1) { d[t][w] = d[s][b] + r1; q.push(P2(d[t][w], P(t, w))); if (t == D) ans = min(ans, d[D][w] + w); } } } cout << ans << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - メンテナンス明け |
User | funcsr |
Language | C++11 (GCC 4.9.2) |
Score | 0 |
Code Size | 1811 Byte |
Status | MLE |
Exec Time | 1133 ms |
Memory | 403604 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 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 | RE | 19 ms | 800 KB |
large/20_large-01 | RE | 16 ms | 796 KB |
large/20_large-02 | RE | 17 ms | 796 KB |
large/20_large-03 | RE | 18 ms | 796 KB |
large/20_large-04 | RE | 17 ms | 796 KB |
large/31_max_large | RE | 18 ms | 732 KB |
small/00_sample00 | AC | 27 ms | 8736 KB |
small/00_sample01 | AC | 27 ms | 8604 KB |
small/00_sample02 | AC | 26 ms | 7064 KB |
small/10_small-0000 | MLE | 534 ms | 396948 KB |
small/10_small-0001 | MLE | 756 ms | 389656 KB |
small/10_small-0002 | MLE | 986 ms | 399636 KB |
small/10_small-0003 | MLE | 872 ms | 399512 KB |
small/10_small-0004 | MLE | 662 ms | 399248 KB |
small/10_small-0005 | MLE | 908 ms | 403604 KB |
small/10_small-0006 | MLE | 562 ms | 396960 KB |
small/10_small-0007 | MLE | 875 ms | 397464 KB |
small/10_small-0008 | MLE | 604 ms | 399132 KB |
small/10_small-0009 | MLE | 525 ms | 396948 KB |
small/10_small-0010 | MLE | 990 ms | 394352 KB |
small/10_small-0011 | MLE | 583 ms | 398996 KB |
small/10_small-0012 | MLE | 587 ms | 399000 KB |
small/10_small-0013 | MLE | 656 ms | 399208 KB |
small/10_small-0014 | MLE | 567 ms | 396964 KB |
small/10_small-0015 | MLE | 615 ms | 386716 KB |
small/10_small-0016 | MLE | 997 ms | 381888 KB |
small/10_small-0017 | MLE | 533 ms | 396900 KB |
small/10_small-0018 | MLE | 680 ms | 399184 KB |
small/10_small-0019 | MLE | 1133 ms | 397528 KB |
small/30_max_small | MLE | 529 ms | 396184 KB |
small/40_simple_0000 | AC | 29 ms | 8608 KB |
small/40_simple_0001 | AC | 26 ms | 8564 KB |
small/40_simple_0002 | AC | 28 ms | 8604 KB |
small/40_simple_0003 | AC | 26 ms | 8604 KB |
small/40_simple_0004 | AC | 28 ms | 8616 KB |
small/40_simple_0005 | AC | 26 ms | 8608 KB |
small/40_simple_0006 | AC | 26 ms | 8564 KB |
small/40_simple_0007 | AC | 27 ms | 8724 KB |
small/40_simple_0008 | AC | 28 ms | 8600 KB |
small/40_simple_0009 | AC | 28 ms | 8728 KB |
small/40_simple_0010 | AC | 27 ms | 8604 KB |
small/40_simple_0011 | AC | 27 ms | 8564 KB |
small/40_simple_0012 | AC | 28 ms | 8608 KB |
small/40_simple_0013 | AC | 28 ms | 8608 KB |
small/40_simple_0014 | AC | 29 ms | 8608 KB |
small/40_simple_0015 | AC | 28 ms | 8612 KB |
small/40_simple_0016 | AC | 28 ms | 8608 KB |
small/40_simple_0017 | AC | 28 ms | 8604 KB |
small/40_simple_0018 | AC | 28 ms | 8612 KB |
small/40_simple_0019 | AC | 27 ms | 8604 KB |
small/90_dijkstra_killer_00 | AC | 39 ms | 17956 KB |
small/90_dijkstra_killer_01 | AC | 38 ms | 17904 KB |
small/91_tayama_killer_00 | AC | 34 ms | 14884 KB |
small/91_tayama_killer_01 | AC | 33 ms | 13212 KB |
small/91_tayama_killer_02 | AC | 36 ms | 16372 KB |
small/91_tayama_killer_03 | AC | 39 ms | 19496 KB |
small/91_tayama_killer_04 | AC | 28 ms | 10144 KB |
small/91_tayama_killer_05 | AC | 38 ms | 16416 KB |