c# - Shortest Path from city 0 to N (by road/ by Air mixed cost) -

okay, need nudge in right direction. have array of costs of travelling city 0 n , array of costs of travelling city 0 n flight. have limit k on number of flights can take when travelling. example

n = 3 // there 3 cities visited 0->1 ->2 ->3 in consecutive order roadtime = { 1, 2, 3}; flighttime = { 2, 1, 6}; k = 2; //take maximum of 2 flights 

i allowed travel road or use road , @ k flights , find minimum cost of travelling 0 3 in example.

what tried:

started out hand trying find possible solution , came binary tree couldn't represent tree structure in code (c#) without pulling hair out - i'm new graphs think applying them. in process of working out stumbled on idea and, thinking had nailed it, realized find permutations of trip 0 n mix of road cost , flight cost minimum cost:

public int mintime(int n, int[] roadtime, int[] flighttime, int k)     {         int n = 0;         int min = roadtime.sum();         while (k > 0)         {             char[] s = (new string('a', n - k) + new string('b', k)).tochararray();                         {                 n = 0;                 (int = 0; < s.length; i++)                 {                     if (s[i] == 'a')                     {                         n += roadtime[i];                     }                     else                     {                         n += flighttime[i];                     }                 }                 min = (n < min) ? n : min;             } while (permute(s));             k--;         }         return min;     }     public boolean permute(char[] a)     {         int n = a.length, = n - 2;         (; >= 0; i--)             if (a[i] < a[i + 1])                 break;         if (i < 0) return false;          (int j = n - 1; j >= i; j--)         {             if (a[j] > a[i])             {                 var temp = a[i];                 a[i] = a[j];                 a[j] = temp;                 break;             }         }         (int j = + 1; j < (n + + 1) / 2; j++)                  {             var temp = a[j];             a[j] = a[n + - j];             a[n + - j] = temp;         }         return true;      } 

this works fine naturally n > 12, there factorial growth in number of permutations of costs. solution works 15 cities in reasonable time. need find way solve problem can find minimum cost 1 no less 50 cities.

even thinking intuitively, how can sure have minimum of if haven't tried them all?

the idea of permutations stuck in head i'm finding hard see way other through present 'rose coloured glasses'. need nudge totally new line of thinking.

any appreciated.

edit!!! 18/may/2014:

found answer after nudge in right direction dukeling. hope else finds useful

public int mintime(int n, int[] roadtime, int[] flighttime, int k)     {         int n = 0;         int min = roadtime.sum();                 {             n = 0;             var sorteddict = (from entry in cost(roadtime, flighttime, n)                               orderby entry.value descending                               entry.value > 0 select entry                    ).take(k)                   .todictionary(pair => pair.key, pair => pair.value);              (int = 0; < n; i++)             {                 if (sorteddict.containskey(i))                 {                     n += flighttime[i];                 }                 else                 {                     n += roadtime[i];                 }             }             min = (n < min) ? n : min;             k--;         } while (k > 0);          return min;     }     static dictionary<int, int> cost (int[] a1, int[] a2, int n)     {         dictionary<int, int> d = new dictionary<int, int>();         for(int = 0; < n; i++)         {             d.add(i, a1[i] - a2[i]);         }         return d;     } 

what want pick flights @ k routes give biggest improvement (and not pick more if there aren't more result in improvement).

so, in example:

roadtime   = { 1, 2, 3}; flighttime = { 2, 1, 6}; improvement    -1 1  -3 

the 1 shows improvement (and biggest improvement) second one, pick flight one.

hint - priority queue might help. no graphs required.