fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <inttypes.h>
  4. #include <math.h>
  5. #include <string.h>
  6.  
  7. #define INF 100000000
  8.  
  9. typedef int keyType;
  10.  
  11. typedef struct node{
  12.     keyType key;
  13.     struct node *parent, *left, *right;
  14. }node;
  15.  
  16. typedef struct heap{
  17.     unsigned int count;
  18.     struct node *root_node, *last_node;
  19. }heap;
  20.  
  21. typedef struct edge{
  22.     int head_vertex, cost;
  23.     struct edge *next;
  24. } edge;
  25.  
  26. typedef struct vertex{
  27.     node heap_node;
  28.     int predecessor, key;
  29.     edge *adjacent;
  30. } vertex;
  31.  
  32. void free_graph(vertex *vertices, int size);
  33.  
  34. void init_graph(vertex *vertices, int size, int source);
  35.  
  36. void insert_edge(vertex *vertices, int tail, int head, int cost);
  37.  
  38. heap* heap_create(void);
  39.  
  40. node* heap_create_node(keyType key);
  41.  
  42. node* heap_insert_child(heap *root);
  43.  
  44. void heap_decrease_key(heap *root, node *heap_node, keyType key);
  45.  
  46. void heap_insert(heap *root, node *heap_node);
  47.  
  48. void heap_swap_left(heap *root, node *heap_node);
  49.  
  50. void heap_swap_right(heap *root, node *heap_node);
  51.  
  52. void heap_increase_key(heap *root, node *heap_node, keyType key);
  53.  
  54. node* heap_find_last(heap *root);
  55.  
  56. node* heap_get_min(heap *root);
  57.  
  58. heap* heap_create(void){
  59.     heap *new_heap = (heap*)malloc(sizeof(heap));
  60.     new_heap->count = 0;
  61.     new_heap->root_node = new_heap->last_node = NULL;
  62.     return new_heap;
  63. }
  64.  
  65. node* heap_create_node(keyType key){
  66.     node *new_node = (node*)malloc(sizeof(node));
  67.     new_node->key = key;
  68.     new_node->parent = new_node->left = new_node->right = NULL;
  69.     return new_node;
  70. }
  71.  
  72.  
  73. node* heap_insert_child(heap *root){
  74.     node *aux = root->last_node;
  75.     unsigned int N = root->count+1;
  76.     if (fabs((int)(log2(N)) - log2(N))<1e-8){
  77.         aux = root->root_node;
  78.         while (aux->left) {
  79.             aux = aux->left;
  80.         }
  81.     }
  82.     else if ( N % 2 == 0){
  83.         while(aux->parent->right == aux)
  84.             aux = aux->parent;
  85.         if(!aux->parent->right)
  86.             return aux->parent;
  87.         aux = aux->parent->right;
  88.         while(aux->left)
  89.             aux = aux->left;
  90.     }
  91.     else{
  92.         aux = aux->parent;
  93.     }
  94.     return aux;
  95. }
  96.  
  97. void heap_decrease_key(heap *root, node *heap_node, keyType key){
  98.     heap_node->key = key;
  99.     node *parent = heap_node->parent;
  100.     node *left = heap_node->left;
  101.     node *right = heap_node->right;
  102.     if(!parent)
  103.         return;
  104.     if(parent->key > heap_node->key){
  105.         if(root->last_node == heap_node)
  106.             root->last_node = parent;
  107.     }
  108.     while(parent && (parent->key > heap_node->key)){
  109.         if(parent->left == heap_node){
  110.             heap_node->left = parent;
  111.             heap_node->right = parent->right;
  112.             if(heap_node->right)
  113.                 heap_node->right->parent = heap_node;
  114.             heap_node->parent = parent->parent;
  115.             if(heap_node->parent){
  116.                 if(heap_node->parent->left == parent)
  117.                     heap_node->parent->left = heap_node;
  118.                 else
  119.                     heap_node->parent->right = heap_node;
  120.             }
  121.             else
  122.                 root->root_node = heap_node;
  123.         }
  124.         else{
  125.             heap_node->right = parent;
  126.             heap_node->left = parent->left;
  127.             if(heap_node->left)
  128.                 heap_node->left->parent = heap_node;
  129.             heap_node->parent = parent->parent;
  130.             if(heap_node->parent){
  131.                 if(heap_node->parent->left == parent)
  132.                     heap_node->parent->left = heap_node;
  133.                 else
  134.                     heap_node->parent->right = heap_node;
  135.             }
  136.             else
  137.                 root->root_node = heap_node;
  138.         }
  139.         parent->left = left;
  140.         parent->right = right;
  141.         parent->parent = heap_node;
  142.         if(left)
  143.             left->parent = parent;
  144.         if(right)
  145.             right->parent = parent;
  146.         parent = heap_node->parent;
  147.         left = heap_node->left;
  148.         right = heap_node->right;
  149.     }
  150. }
  151.  
  152. void heap_insert(heap *root, node *heap_node){
  153.  
  154.     node *parent = NULL;
  155.     heap_node->parent = heap_node->left = heap_node->right = NULL;
  156.  
  157.     if(!root->count){
  158.         root->root_node = root->last_node = heap_node;
  159.         root->count++;
  160.     }
  161.     else{
  162.         parent = heap_insert_child(root);
  163.         if(parent->left){
  164.             parent->right = heap_node;
  165.         }
  166.         else{
  167.             parent->left = heap_node;
  168.         }
  169.         heap_node->parent = parent;
  170.         root->count++;
  171.         root->last_node = heap_node;
  172.         heap_decrease_key(root, heap_node, heap_node->key);
  173.     }
  174. }
  175.  
  176.  
  177. void heap_swap_left(heap *root, node *heap_node){
  178.     node *parent = heap_node->parent;
  179.     node *left = heap_node->left;
  180.     node *right = heap_node->right;
  181.  
  182.     heap_node->parent = left;
  183.     heap_node->left = left->left;
  184.     if(heap_node->left)
  185.         heap_node->left->parent = heap_node;
  186.     heap_node->right = left->right;
  187.     if(heap_node->right)
  188.         heap_node->right->parent = heap_node;
  189.  
  190.     left->parent = parent;
  191.     if(parent){
  192.         if(parent->left == heap_node)
  193.             parent->left = left;
  194.         else
  195.             parent->right = left;
  196.     }
  197.     else
  198.         root->root_node = left;
  199.     left->left = heap_node;
  200.     left->right = right;
  201.     if(right)
  202.         right->parent = left;
  203.     if(root->last_node == left)
  204.         root->last_node = heap_node;
  205. }
  206.  
  207. void heap_swap_right(heap *root, node *heap_node){
  208.     node *parent = heap_node->parent;
  209.     node *left = heap_node->left;
  210.     node *right = heap_node->right;
  211.  
  212.     heap_node->parent = right;
  213.     heap_node->left = right->left;
  214.     if(heap_node->left)
  215.         heap_node->left->parent = heap_node;
  216.     heap_node->right = right->right;
  217.     if(heap_node->right)
  218.         heap_node->right->parent = heap_node;
  219.  
  220.     right->parent = parent;
  221.     if(parent){
  222.         if(parent->left == heap_node)
  223.             parent->left = right;
  224.         else
  225.             parent->right = right;
  226.     }
  227.     else
  228.         root->root_node = right;
  229.     right->right = heap_node;
  230.     right->left = left;
  231.     if(left)
  232.         left->parent = right;
  233.     if(root->last_node == right)
  234.         root->last_node = heap_node;
  235. }
  236.  
  237. void heap_increase_key(heap *root, node *heap_node, keyType key){
  238.     heap_node->key = key;
  239.     node *left = heap_node->left;
  240.     node *right = heap_node->right;
  241.     if(left && (heap_node->key > left->key)){
  242.         if(right && (heap_node->key > right->key)){
  243.             if(left->key < right->key)
  244.                 heap_swap_left(root, heap_node);
  245.             else
  246.                 heap_swap_right(root, heap_node);
  247.         }
  248.         else
  249.             heap_swap_left(root, heap_node);
  250.         heap_increase_key(root, heap_node, key);
  251.     }
  252.     else if(right && (heap_node->key > right->key)){
  253.         heap_swap_right(root, heap_node);
  254.         heap_increase_key(root, heap_node, key);
  255.     }
  256. }
  257.  
  258. node* heap_find_last(heap *root){
  259.     node *aux = root->last_node;
  260.     unsigned int N = root->count+1;
  261.     if (fabs((int)(log2(N)) - log2(N))<1e-8){
  262.         aux = root->root_node;
  263.         while (aux->right) {
  264.             aux = aux->right;
  265.         }
  266.     }
  267.     else if ( N % 2 == 0){
  268.         while(aux->parent->left == aux)
  269.             aux = aux->parent;
  270.         aux = aux->parent->left;
  271.         while(aux->right)
  272.             aux = aux->right;
  273.     }
  274.     return aux;
  275. }
  276.  
  277. node *heap_get_min(heap *root){
  278.     node *min_node = root->root_node;
  279.     node *new_min = root->last_node;
  280.     if(!min_node)
  281.         return NULL;
  282.     root->count--;
  283.     if(root->count == 0){
  284.         root->last_node = root->root_node = NULL;
  285.         return min_node;
  286.     }
  287.     if(root->count == 1){
  288.         root->last_node = root->root_node = new_min;
  289.         new_min->parent = NULL;
  290.         return min_node;
  291.     }
  292.     else{
  293.         if(new_min->parent->left == new_min){
  294.             new_min->parent->left = NULL;
  295.             root->last_node = new_min->parent;
  296.             root->last_node = heap_find_last(root);
  297.         }
  298.         else{
  299.             new_min->parent->right = NULL;
  300.             root->last_node = new_min->parent->left;
  301.         }
  302.         new_min->left = min_node->left;
  303.         if(new_min->left)
  304.             new_min->left->parent = new_min;
  305.         new_min->right = min_node->right;
  306.         if (new_min->right)
  307.             new_min->right->parent = new_min;
  308.         new_min->parent = NULL;
  309.         root->root_node = new_min;
  310.         heap_increase_key(root, new_min, new_min->key);
  311.     }
  312.     return min_node;
  313. }
  314.  
  315. void init_graph(vertex *vertices, int size, int source){
  316.  
  317.     int i;
  318.     for(i=0; i<size; i++) {
  319.         vertices[i].predecessor = -1;
  320.         vertices[i].adjacent = NULL;
  321.         vertices[i].key = i;
  322.         vertices[i].heap_node.key = INF;
  323.         vertices[i].heap_node.parent = NULL;
  324.         vertices[i].heap_node.left = NULL;
  325.         vertices[i].heap_node.right = NULL;
  326.     }
  327.     vertices[source].heap_node.key = 0;
  328. }
  329.  
  330. void insert_edge(vertex *vertices, int tail, int head, int cost){
  331.  
  332.     edge *new_edge = (edge*)malloc(sizeof(edge));
  333.     new_edge->next = vertices[tail].adjacent;
  334.     new_edge->head_vertex = head;
  335.     new_edge->cost = cost;
  336.     vertices[tail].adjacent = new_edge;
  337. }
  338.  
  339. void free_graph(vertex *vertices, int size){
  340.  
  341.     int i;
  342.     edge *aux, *aux2;
  343.     if(!vertices)
  344.         return;
  345.     for(i=0; i<size; i++){
  346.         aux = vertices[i].adjacent;
  347.         while(aux){
  348.             aux2 = aux->next;
  349.             free(aux);
  350.             aux = aux2;
  351.         }
  352.     }
  353. }
  354.  
  355. void dijkstra(vertex *vertices, heap *root){
  356. 	int new_cost, adjacent;
  357. 	node *min_node;
  358. 	vertex *min_vertex, *adjacent_vertex;
  359. 	while(root->root_node){
  360. 		min_node = heap_get_min(root);
  361. 		min_vertex = (vertex*)min_node;
  362. 		edge *aux = min_vertex->adjacent;
  363. 		while(aux){
  364. 			adjacent = aux->head_vertex;
  365. 			new_cost = min_vertex->heap_node.key + aux->cost;
  366. 			adjacent_vertex = &(vertices[adjacent]);
  367. 			if(new_cost < adjacent_vertex->heap_node.key){
  368. 				if(adjacent_vertex->heap_node.key == INF){
  369. 					adjacent_vertex->heap_node.key = new_cost;
  370. 					heap_insert(root, &(adjacent_vertex->heap_node));
  371. 				}
  372. 				else{
  373. 					heap_decrease_key(root, &(adjacent_vertex->heap_node), new_cost);
  374. 				}
  375. 				adjacent_vertex->predecessor = min_vertex->key;
  376. 				adjacent_vertex->heap_node.key = new_cost;
  377. 			}
  378. 			aux = aux->next;
  379. 		}
  380. 	}
  381. }
  382.  
  383. int main(void){
  384.     int n, m, n0, m0, n1, m1;
  385.     scanf("%d%d%d%d%d%d", &n, &m, &n0, &m0, &n1, &m1);
  386.     short map[n][m];
  387.     for(int i=0; i<n; i++){
  388.         for(int j=0; j<m; j++){
  389.             scanf("%hd",&map[i][j]);
  390.         }
  391.     }
  392.     int to=n1+m1*n;
  393.     int from=n0+m0*n;
  394.     if(n1==n0&&m1==m0){
  395.         printf("0");
  396.         return 0;
  397.     }
  398.     heap *root = heap_create();
  399.     vertex *v=malloc(n*m*sizeof(vertex));
  400.     init_graph(v,m*n,from);
  401.     heap_insert(root, &(v[from].heap_node));
  402.     for(int i=0;i<n;i++){
  403.         for(int j=0; j<m; j++){
  404.             if(i>0){
  405.                 int diff=abs(map[i][j]-map[i-1][j]);
  406.                 insert_edge(v,i+n*j,i-1+n*j,diff);
  407.             }
  408.             if(i<n-1){
  409.                 int diff=abs(map[i][j]-map[i+1][j]);
  410.                 insert_edge(v,i+n*j,i+1+n*j,diff);
  411.             }
  412.             if(j>0){
  413.                 int diff=abs(map[i][j]-map[i][j-1]);
  414.                 insert_edge(v,i+n*j,i+n*(j-1),diff);
  415.             }
  416.             if(j<m-1){
  417.                 int diff=abs(map[i][j]-map[i][j+1]);
  418.                 insert_edge(v,i+n*j,i+n*(j+1),diff);
  419.             }
  420.         }
  421.     }
  422.  
  423.     dijkstra(v,root);
  424.     printf("%d",v[to].heap_node.key);
  425.  
  426.     free_graph(v, n*m);
  427.     free(root);
  428.     free(v);
  429.     return 0;
  430. }
  431.  
Success #stdin #stdout 0s 4388KB
comments ()
stdin 
2 2 0 0 1 1
0 10
30 20
stdout 
20
https://ideone.com/tNQSxJ
language:
C99 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!