daily pastebin goal
9%
SHARE
TWEET

Untitled

a guest Aug 13th, 2017 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. namespace RoadsNLibraries
  8. {
  9.     class RoadsNLibraries
  10.     {
  11.         static Dictionary<int, List<int>> adj = new Dictionary<int, List<int>>();
  12.         static List<bool> visited = new List<bool>();
  13.         static int nodes = 0;
  14.         static long cost = 0;
  15.  
  16.         static void DFS(int n)
  17.         {
  18.             nodes++;
  19.             visited[n] = true;
  20.             foreach (int i in adj[n])
  21.             {
  22.                 if (!visited[i])
  23.                 {
  24.                     DFS(i);
  25.                 }
  26.             }
  27.             return;
  28.         }
  29.  
  30.         static void clear()
  31.         {
  32.             adj.Clear();
  33.             cost = 0;
  34.             nodes = 0;
  35.         }
  36.  
  37.         static void Main(String[] args)
  38.         {
  39.  
  40.             int q = Convert.ToInt32(Console.ReadLine());
  41.             for (int a0 = 0; a0 < q; a0++)
  42.             {
  43.                 string[] tokens_n = Console.ReadLine().Split(' ');
  44.                 int n = Convert.ToInt32(tokens_n[0]);
  45.                 int m = Convert.ToInt32(tokens_n[1]);
  46.                 long x = Convert.ToInt64(tokens_n[2]);
  47.                 long y = Convert.ToInt64(tokens_n[3]);
  48.  
  49.  
  50.                 for (int a1 = 0; a1 < m; a1++)
  51.                 {
  52.                     string[] tokens_city_1 = Console.ReadLine().Split(' ');
  53.                     int city_1 = Convert.ToInt32(tokens_city_1[0]);
  54.                     int city_2 = Convert.ToInt32(tokens_city_1[1]);
  55.                     if (adj.ContainsKey(city_1))
  56.                     {
  57.                         adj[city_1].Add(city_2);
  58.                     }
  59.                     else
  60.                     {
  61.                         adj.Add(city_1, new List<int>() { city_2 });
  62.                     }
  63.                     if (adj.ContainsKey(city_2))
  64.                     {
  65.                         adj[city_2].Add(city_1);
  66.                     }
  67.                     else
  68.                     {
  69.                         adj.Add(city_2, new List<int>() { city_1 });
  70.                     }
  71.  
  72.                 }
  73.  
  74.                 cost = 0;
  75.                 visited = Enumerable.Repeat(false, n + 1).ToList();
  76.                 for (int i = 1; i <= n; ++i)
  77.                 {
  78.  
  79.                     if (!visited[i])
  80.                     {
  81.                         if(adj.ContainsKey(i))
  82.                             DFS(i);
  83.                         cost = cost + x;
  84.                         if (x > y)
  85.                             cost = cost + (y * Math.Max(0,(nodes - 1)));
  86.                         else
  87.                             cost = cost + (x * Math.Max(0, (nodes - 1)));
  88.  
  89.                     }
  90.                 }
  91.  
  92.                 Console.WriteLine(cost);
  93.                 clear();
  94.             }
  95.             Console.Read();
  96.         }
  97.     }
  98. }
RAW Paste Data
Top