Submission #1334285
Source Code Expand
using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.IO; using System.Text; using System.Globalization; using System.Diagnostics; class Myon { public Myon() { } public static int Main() { new Myon().calc(); return 0; } Scanner cin; List<Tuple<int, int, int, int>>[] es; //next, cost, final, finalcost; long[] dist; long[] dist2; long MAX = (long)1e18; void calc() { cin = new Scanner(); int N = cin.nextInt(); int M = cin.nextInt(); int start = cin.nextInt(); int goal = cin.nextInt(); es = new List<Tuple<int, int, int, int>>[N]; for (int i = 0; i < N; i++) { es[i] = new List<Tuple<int, int, int, int>>(); } for (int i = 0; i < M; i++) { int L = cin.nextInt(); int[] s = new int[L]; int[] w = new int[L - 1]; for (int j = 0; j < L; j++) { s[j] = cin.nextInt(); } int sum = 0; for (int j = 0; j < L - 1; j++) { w[j] = cin.nextInt(); sum += w[j]; } int now = 0; for (int j = 0; j < L - 1; j++) { es[s[j]].Add(Tuple.Create(s[j + 1], w[j], s[0], now + w[j])); es[s[j + 1]].Add(Tuple.Create(s[j], w[j], s[L - 1], sum - now)); //Console.WriteLine("{0} {1} {2} {3}", s[j + 1], w[j], s[L - 1], sum - now); now += w[j]; } } dist = new long[N]; dist2 = new long[N]; for (int i = 0; i < N; i++) { dist[i] = dist2[i] = MAX; } dist[goal] = dist2[goal] = 0; Heap<long> h; h = new Heap<long>(); h.push(goal); while(h.top != null) { var nowP = h.pop(); int now = (int)(nowP & 0xFFFF); long nowCost = (nowP >> 16); if (nowCost != dist[now]) continue; foreach (var e in es[now]) { int next = e.Item1; long nextCost = dist[now] + e.Item2; if(nextCost < dist[next]) { dist[next] = nextCost; h.push((nextCost << 16) + next); } } } h = new Heap<long>(); h.push(goal); while (h.top != null) { var nowP = h.pop(); int now = (int)(nowP & 0xFFFF); long nowCost = (nowP >> 16); if (nowCost != dist2[now]) continue; foreach (var e in es[now]) { int next = e.Item1; long nextCost = dist2[now] + e.Item2; nextCost = Math.Max(nextCost, e.Item4 + dist[e.Item3]); if (nextCost < dist2[next]) { dist2[next] = nextCost; h.push((nextCost << 16) + next); } } } Console.WriteLine(dist2[start]); } class Heap<T> where T : IComparable { public HeapNode<T> top; public Heap() { } public void push(T val) { top = HeapNode<T>.meld(top, new HeapNode<T>(val)); } public T pop() { T ret = top.val; top = HeapNode<T>.meld(top.r, top.l); return ret; } public void merge(Heap<T> h2) { top = HeapNode<T>.meld(top, h2.top); } public class HeapNode<NT> where NT : IComparable { public HeapNode<NT> l, r; public NT val; public HeapNode(NT _val) { val = _val; } public static HeapNode<NT> meld(HeapNode<NT> a, HeapNode<NT> b) { if (a == null) return b; if (b == null) return a; if (a.val.CompareTo(b.val) > 0) { HeapNode<NT> temp = a; a = b; b = temp; } a.r = meld(a.r, b); HeapNode<NT> temph = a.l; a.l = a.r; a.r = temph; return a; } } } } class Scanner { string[] s; int i; char[] cs = new char[] { ' ' }; public Scanner() { s = new string[0]; i = 0; } public string next() { if (i < s.Length) return s[i++]; string st = Console.ReadLine(); while (st == "") st = Console.ReadLine(); s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries); i = 0; return s[i++]; } public int nextInt() { return int.Parse(next()); } public long nextLong() { return long.Parse(next()); } public double nextDouble() { return double.Parse(next()); } }
Submission Info
Submission Time | |
---|---|
Task | C - メンテナンス明け |
User | chokudai |
Language | C# (Mono 4.6.2.0) |
Score | 100 |
Code Size | 5335 Byte |
Status | AC |
Exec Time | 149 ms |
Memory | 28488 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 | 146 ms | 25208 KB |
large/20_large-01 | AC | 149 ms | 23032 KB |
large/20_large-02 | AC | 147 ms | 24948 KB |
large/20_large-03 | AC | 145 ms | 24820 KB |
large/20_large-04 | AC | 147 ms | 27000 KB |
large/31_max_large | AC | 58 ms | 28488 KB |
small/00_sample00 | AC | 23 ms | 9172 KB |
small/00_sample01 | AC | 24 ms | 13268 KB |
small/00_sample02 | AC | 24 ms | 13268 KB |
small/10_small-0000 | AC | 25 ms | 13268 KB |
small/10_small-0001 | AC | 24 ms | 11348 KB |
small/10_small-0002 | AC | 24 ms | 11348 KB |
small/10_small-0003 | AC | 25 ms | 11220 KB |
small/10_small-0004 | AC | 24 ms | 11220 KB |
small/10_small-0005 | AC | 24 ms | 9300 KB |
small/10_small-0006 | AC | 25 ms | 13268 KB |
small/10_small-0007 | AC | 24 ms | 11220 KB |
small/10_small-0008 | AC | 24 ms | 11348 KB |
small/10_small-0009 | AC | 24 ms | 11348 KB |
small/10_small-0010 | AC | 24 ms | 11348 KB |
small/10_small-0011 | AC | 24 ms | 9300 KB |
small/10_small-0012 | AC | 24 ms | 9300 KB |
small/10_small-0013 | AC | 24 ms | 9300 KB |
small/10_small-0014 | AC | 24 ms | 11348 KB |
small/10_small-0015 | AC | 29 ms | 11220 KB |
small/10_small-0016 | AC | 24 ms | 9172 KB |
small/10_small-0017 | AC | 25 ms | 13268 KB |
small/10_small-0018 | AC | 24 ms | 11220 KB |
small/10_small-0019 | AC | 24 ms | 9300 KB |
small/30_max_small | AC | 24 ms | 11348 KB |
small/40_simple_0000 | AC | 24 ms | 11348 KB |
small/40_simple_0001 | AC | 24 ms | 13268 KB |
small/40_simple_0002 | AC | 23 ms | 11220 KB |
small/40_simple_0003 | AC | 23 ms | 9300 KB |
small/40_simple_0004 | AC | 24 ms | 11348 KB |
small/40_simple_0005 | AC | 23 ms | 9172 KB |
small/40_simple_0006 | AC | 23 ms | 9300 KB |
small/40_simple_0007 | AC | 24 ms | 13396 KB |
small/40_simple_0008 | AC | 23 ms | 9172 KB |
small/40_simple_0009 | AC | 24 ms | 11348 KB |
small/40_simple_0010 | AC | 24 ms | 11220 KB |
small/40_simple_0011 | AC | 25 ms | 13268 KB |
small/40_simple_0012 | AC | 24 ms | 11348 KB |
small/40_simple_0013 | AC | 24 ms | 11220 KB |
small/40_simple_0014 | AC | 23 ms | 9172 KB |
small/40_simple_0015 | AC | 23 ms | 9300 KB |
small/40_simple_0016 | AC | 24 ms | 13268 KB |
small/40_simple_0017 | AC | 24 ms | 11220 KB |
small/40_simple_0018 | AC | 24 ms | 11348 KB |
small/40_simple_0019 | AC | 24 ms | 11348 KB |
small/90_dijkstra_killer_00 | AC | 24 ms | 11220 KB |
small/90_dijkstra_killer_01 | AC | 23 ms | 11220 KB |
small/91_tayama_killer_00 | AC | 23 ms | 11348 KB |
small/91_tayama_killer_01 | AC | 24 ms | 13268 KB |
small/91_tayama_killer_02 | AC | 24 ms | 11220 KB |
small/91_tayama_killer_03 | AC | 24 ms | 11348 KB |
small/91_tayama_killer_04 | AC | 24 ms | 11348 KB |
small/91_tayama_killer_05 | AC | 24 ms | 13268 KB |