fork download
copy 
  1. using static IO;
  2. public class IO{
  3. public static IO Cin=new();
  4. public static StreamReader reader=new(Console.OpenStandardInput());
  5. public static StreamWriter writer=new(Console.OpenStandardOutput());
  6. public static implicit operator string(IO _)=>reader.ReadLine();
  7. public static implicit operator char[](IO _)=>reader.ReadLine().ToArray();
  8. public static implicit operator int(IO _)=>int.Parse(reader.ReadLine());
  9. public static implicit operator double(IO _)=>double.Parse(reader.ReadLine());
  10. public static implicit operator string[](IO _)=>reader.ReadLine().Split();
  11. public static implicit operator int[](IO _)=>Array.ConvertAll(reader.ReadLine().Split(),int.Parse);
  12. public static implicit operator (int,int)(IO _){int[] a=Cin;return(a[0],a[1]);}
  13. public static implicit operator (int,int,int)(IO _){int[] a=Cin;return(a[0],a[1],a[2]);}
  14. public void Deconstruct(out int a,out int b){(int,int) r=Cin;(a,b)=r;}
  15. public void Deconstruct(out int a,out int b,out int c){(int,int,int) r=Cin;(a,b,c)=r;}
  16. public static void Loop(int end,Action<int> action,int start = 0,in int add = 1){for(;start<end;start+=add)action(start);}
  17. public static void Loop(int end,Func<int,bool> action,int start = 0,in int add = 1){for(;start<end && action(start) ; start+=add);}
  18. public static object? Cout{set{writer.Write(value);}}
  19. public static object? Coutln{set{writer.WriteLine(value);}}
  20. public static void Main() {checked{Program.Coding();}writer.Flush();}
  21. }
  22. class Program
  23. {
  24.     public static void Coding()
  25.     {
  26.         (int nodeCount, int lineCount) = Cin;
  27.         Graph graph = new(nodeCount);
  28.         Loop(lineCount, _ =>
  29.         {
  30.             (int a, int b) = Cin;
  31.             graph.AddTwoWay(--a, --b);
  32.         });
  33.  
  34.         int[] dist2zero = graph.GetDistance(0);
  35.         #if DEBUG
  36.         foreach (var r in Enumerable.Range(0, nodeCount).Select(i => $"dist2zero[{i}] : {dist2zero[i]}")) Coutln = r;
  37.         #endif
  38.  
  39.         Queue<int> queue = new();
  40.         bool[] visited = new bool[nodeCount];
  41.         visited[nodeCount - 1] = true;
  42.         foreach (int next in graph.Lines[nodeCount - 1])
  43.         {
  44.             if (next == 0)
  45.             {
  46.                 Cout = 1;
  47.                 return;
  48.             }
  49.             visited[next] = true;
  50.             if (dist2zero[next] > dist2zero[^1] - 1) continue;
  51.             queue.Enqueue(next);
  52.         }
  53.  
  54.         HashSet<int> shortable = new();
  55.  
  56.         for (int d = dist2zero[^1]-2; visited[0] is false; d--)
  57.         {
  58. #if DEBUG
  59.             Coutln = $"queue: {string.Join(' ', queue)}";
  60. #endif
  61.             int remain = queue.Count;
  62.             if (remain == 1)
  63.             {
  64.                 Cout = queue.Dequeue() + 1;
  65.                 return;
  66.             }
  67.  
  68.             for (; remain > 0; remain--)
  69.             {
  70.                 int from = queue.Dequeue();
  71.                 foreach (int to in graph.Lines[from])
  72.                 {
  73.                     if (to == 0)
  74.                     {
  75.                         shortable.Add(from);
  76.                     }
  77.                     if (visited[to]) continue;
  78.                     visited[to] = true;
  79.                     if (dist2zero[to] > d) continue;
  80.                     queue.Enqueue(to);
  81.                 }
  82.             }
  83.         }
  84.  
  85.         Cout = shortable.Count == 1 ? (shortable.First() + 1) : 1;
  86.     }
  87. }
  88.  
  89. class Graph
  90. {
  91.     public Graph(int size)
  92.     {
  93.         Lines = new LinkedList<int>[NodeCount = size];
  94.         for (int i = 0; i < size; i++) Lines[i] = new();
  95.     }
  96.  
  97.     public void AddTwoWay(int a, int b)
  98.     {
  99.         Lines[a].AddLast(b);
  100.         Lines[b].AddLast(a);
  101.     }
  102.  
  103.     public int[] GetDistance(int starting)
  104.     {
  105.         Queue<int> queue = new();
  106.         queue.Enqueue(starting);
  107.  
  108.         int[] dist = Enumerable.Repeat(int.MaxValue, NodeCount).ToArray();
  109.         for (int distance = 0; queue.Count > 0; distance++)
  110.         {
  111.             for (int remain = queue.Count; remain > 0; remain--)
  112.             {
  113.                 int from = queue.Dequeue();
  114.                 if (dist[from] != int.MaxValue) continue;
  115.                 dist[from] = distance;
  116.                 foreach (int to in Lines[from])
  117.                 {
  118.                     queue.Enqueue(to);
  119.                 }
  120.             }
  121.         }
  122.  
  123.         return dist;
  124.     }
  125.     public int NodeCount { get; }    
  126.     public LinkedList<int>[] Lines { get; }
  127. }
Success #stdin #stdout 0.06s 29632KB
comments (?)
stdin
copy 
6 7
1 2
2 4
4 6
1 3
3 4
4 5
5 6
stdout
copy 
dist2zero[0] : 0
dist2zero[1] : 1
dist2zero[2] : 1
dist2zero[3] : 2
dist2zero[4] : 3
dist2zero[5] : 3
queue: 3
4
https://ideone.com/fdY719
language:
C# (NET 6.0)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!