fork download
  1. #include <iostream>
  2. #define fr(i,n) for(int i=1; i<=n; i++)
  3. #define mp make_pair
  4. #define MXN 1010
  5.  
  6. using namespace std;
  7.  
  8. int prev_min_ind[MXN], mincost[MXN], used[MXN];
  9. int pr,tmincost,n,m,k,w;
  10. pair<int,int > ans[MXN];
  11. char lvl[MXN][15][15];
  12.  
  13. int main() {
  14. cin>>n>>m>>k>>w;
  15.  
  16. fr(i,k) fr(j,n) cin>>lvl[i][j];
  17.  
  18. fr(i,k) mincost[i]=n*m, prev_min_ind[i]=0;
  19. //1 is considered exclusively so i'm assuming prev sent was 1, note that
  20. //this val wouldn't affect answer, you could send any level for first time so
  21. //you could pr any val as far as pr<=k and print this chosen val exclusively
  22. pr=1;
  23. //i need atmost k-1 iterations as i have already chosen 1 vertex but still i need to choose k-1 nodes
  24. //since in each iteration i'll choose at least(exactly) one node so max iterations = k - 1
  25. //this is a very good implementation of prim's algo.
  26. fr(i,k-1){
  27. used[pr] = 1;
  28. int cmincost = 10000, fminind = 0;
  29. //search over all vertices which one gives min cost for sending after pr vertex if this is not used already
  30. fr(x,k) if(!used[x]){
  31. int cst=0;
  32. //find cost of lvl x sending after level pr(if it will be sent in future after 1)
  33. fr(y,n) for(int c=0; c<m; ++c) if(lvl[pr][y][c] != lvl[x][y][c]) cst += w;
  34. //if this cost is less than any other cost, update values
  35. if(mincost[x]>cst){ mincost[x] = cst; prev_min_ind[x]=pr; }
  36. /**
  37.   *
  38.   * if choosing this x vertex gives me the lowest cost update current min out of all
  39.   * note that we are updating prev_min_ind array bcoz this min value might have come from some
  40.   * prev iteration of i when it was min in that iteration but in this iteration it became min
  41.   * so if this is the case prev_min_ind already have proper value, for second case it must have been
  42.   * modified in upper if block
  43.   */
  44. if(mincost[x]<cmincost){ cmincost=mincost[x]; fminind=x; }
  45. }
  46. tmincost += cmincost;
  47. pr = fminind;
  48. ans[i] = mp(pr, prev_min_ind[pr]);
  49. }
  50. cout<<tmincost+m*n<<endl;
  51. printf("1 0\n");
  52. fr(i,k-1) printf("%d %d\n",ans[i].first,ans[i].second);
  53. }
  54.  
Success #stdin #stdout 0s 15480KB
stdin
1 3 5 2
ABA
BBB
BBA
BAB
ABB
stdout
11
1 0
3 1
2 3
4 2
5 1