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.             queue.Enqueue(next);
  51.         }
  52.  
  53.         HashSet<int> shortable = new();
  54.  
  55.         for (int d = dist2zero[^1]-2; visited[0] is false; d--)
  56.         {
  57. #if DEBUG
  58.             Coutln = $"queue: {string.Join(' ', queue)}";
  59. #endif
  60.             int remain = queue.Count;
  61.             if (remain == 1)
  62.             {
  63.                 Cout = queue.Dequeue() + 1;
  64.                 return;
  65.             }
  66.  
  67.             for (; remain > 0; remain--)
  68.             {
  69.                 int from = queue.Dequeue();
  70.                 foreach (int to in graph.Lines[from])
  71.                 {
  72.                     if (to == 0)
  73.                     {
  74.                         shortable.Add(from);
  75.                     }
  76.                     if (visited[to]) continue;
  77.                     visited[to] = true;
  78.                     if (dist2zero[to] > d) continue;
  79.                     queue.Enqueue(to);
  80.                 }
  81.             }
  82.         }
  83.  
  84.         Cout = shortable.Count == 1 ? (shortable.First() + 1) : 1;
  85.     }
  86. }
  87.  
  88. class Graph
  89. {
  90.     public Graph(int size)
  91.     {
  92.         Lines = new LinkedList<int>[NodeCount = size];
  93.         for (int i = 0; i < size; i++) Lines[i] = new();
  94.     }
  95.  
  96.     public void AddTwoWay(int a, int b)
  97.     {
  98.         Lines[a].AddLast(b);
  99.         Lines[b].AddLast(a);
  100.     }
  101.  
  102.     public int[] GetDistance(int starting)
  103.     {
  104.         Queue<int> queue = new();
  105.         queue.Enqueue(starting);
  106.  
  107.         int[] dist = Enumerable.Repeat(int.MaxValue, NodeCount).ToArray();
  108.         for (int distance = 0; queue.Count > 0; distance++)
  109.         {
  110.             for (int remain = queue.Count; remain > 0; remain--)
  111.             {
  112.                 int from = queue.Dequeue();
  113.                 if (dist[from] != int.MaxValue) continue;
  114.                 dist[from] = distance;
  115.                 foreach (int to in Lines[from])
  116.                 {
  117.                     queue.Enqueue(to);
  118.                 }
  119.             }
  120.         }
  121.  
  122.         return dist;
  123.     }
  124.     public int NodeCount { get; }    
  125.     public LinkedList<int>[] Lines { get; }
  126. }
Success #stdin #stdout 0.09s 31808KB
comments (?)
stdin
copy 
11 13
1 2
1 3
2 4
3 4
4 5
4 6
5 11
6 11
1 7
7 8
8 9
9 10
10 11
stdout
copy 
dist2zero[0] : 0
dist2zero[1] : 1
dist2zero[2] : 1
dist2zero[3] : 2
dist2zero[4] : 3
dist2zero[5] : 3
dist2zero[6] : 1
dist2zero[7] : 2
dist2zero[8] : 3
dist2zero[9] : 4
dist2zero[10] : 4
queue: 4 5 9
queue: 3
4
https://ideone.com/FbFZB0
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!