Submission #1027038
Source Code Expand
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <queue> using namespace std; #define INF (1LL<<60) #define MAX_B 120000 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 | WA |
Exec Time | 951 ms |
Memory | 246164 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 | 792 KB |
large/20_large-02 | RE | 18 ms | 928 KB |
large/20_large-03 | RE | 19 ms | 796 KB |
large/20_large-04 | RE | 16 ms | 800 KB |
large/31_max_large | RE | 18 ms | 924 KB |
small/00_sample00 | AC | 25 ms | 5536 KB |
small/00_sample01 | AC | 24 ms | 5536 KB |
small/00_sample02 | AC | 23 ms | 4640 KB |
small/10_small-0000 | WA | 363 ms | 239376 KB |
small/10_small-0001 | AC | 584 ms | 235164 KB |
small/10_small-0002 | WA | 805 ms | 242188 KB |
small/10_small-0003 | WA | 690 ms | 242060 KB |
small/10_small-0004 | WA | 489 ms | 241772 KB |
small/10_small-0005 | WA | 736 ms | 246164 KB |
small/10_small-0006 | WA | 395 ms | 239516 KB |
small/10_small-0007 | WA | 703 ms | 240016 KB |
small/10_small-0008 | AC | 429 ms | 241648 KB |
small/10_small-0009 | WA | 351 ms | 239384 KB |
small/10_small-0010 | WA | 814 ms | 238116 KB |
small/10_small-0011 | WA | 414 ms | 241556 KB |
small/10_small-0012 | WA | 410 ms | 241556 KB |
small/10_small-0013 | WA | 477 ms | 241688 KB |
small/10_small-0014 | AC | 396 ms | 239472 KB |
small/10_small-0015 | WA | 448 ms | 234136 KB |
small/10_small-0016 | WA | 821 ms | 233056 KB |
small/10_small-0017 | WA | 357 ms | 239464 KB |
small/10_small-0018 | WA | 506 ms | 241764 KB |
small/10_small-0019 | WA | 951 ms | 242448 KB |
small/30_max_small | AC | 343 ms | 238616 KB |
small/40_simple_0000 | AC | 23 ms | 5532 KB |
small/40_simple_0001 | AC | 24 ms | 5532 KB |
small/40_simple_0002 | AC | 24 ms | 5408 KB |
small/40_simple_0003 | AC | 24 ms | 5408 KB |
small/40_simple_0004 | AC | 23 ms | 5536 KB |
small/40_simple_0005 | AC | 22 ms | 5532 KB |
small/40_simple_0006 | AC | 24 ms | 5536 KB |
small/40_simple_0007 | AC | 22 ms | 5412 KB |
small/40_simple_0008 | AC | 24 ms | 5528 KB |
small/40_simple_0009 | AC | 23 ms | 5528 KB |
small/40_simple_0010 | AC | 24 ms | 5408 KB |
small/40_simple_0011 | AC | 24 ms | 5536 KB |
small/40_simple_0012 | AC | 22 ms | 5528 KB |
small/40_simple_0013 | AC | 25 ms | 5532 KB |
small/40_simple_0014 | AC | 23 ms | 5532 KB |
small/40_simple_0015 | AC | 24 ms | 5532 KB |
small/40_simple_0016 | AC | 24 ms | 5536 KB |
small/40_simple_0017 | AC | 24 ms | 5408 KB |
small/40_simple_0018 | AC | 23 ms | 5408 KB |
small/40_simple_0019 | AC | 22 ms | 5528 KB |
small/90_dijkstra_killer_00 | AC | 29 ms | 11124 KB |
small/90_dijkstra_killer_01 | AC | 30 ms | 11036 KB |
small/91_tayama_killer_00 | AC | 27 ms | 9204 KB |
small/91_tayama_killer_01 | AC | 26 ms | 8344 KB |
small/91_tayama_killer_02 | AC | 30 ms | 10152 KB |
small/91_tayama_killer_03 | AC | 31 ms | 12056 KB |
small/91_tayama_killer_04 | AC | 24 ms | 6432 KB |
small/91_tayama_killer_05 | AC | 28 ms | 10136 KB |