fork download 
  1. #include <stdio.h> 
  2. #include <stdlib.h> 
  3. #include <assert.h> 
  4.  
  5. typedef struct Queue Queue;
  6.  
  7. struct Queue {
  8.     int data;
  9.     int priority;
  10.     Queue *next;
  11. };
  12.  
  13. Queue *queue_new(int d, int p)
  14. {
  15.     Queue *n = malloc(sizeof(*n));
  16.  
  17.     n->data = d;
  18.     n->priority = p;
  19.     n->next = NULL;
  20.  
  21.     return n;
  22. }
  23.  
  24. int queue_pop(Queue **head)
  25. {
  26.     assert(*head);
  27.  
  28.     Queue *old = *head;
  29.     int res = old->data;
  30.  
  31.     *head = (*head)->next;
  32.     free(old);
  33.  
  34.     return res;
  35. }
  36.  
  37. void queue_remove(Queue **head, int data)
  38. {
  39.     while (*head && (*head)->data != data) {
  40.         head = &(*head)->next;
  41.     }
  42.  
  43.     if (*head) queue_pop(head);
  44. }
  45.  
  46. void queue_push(Queue **head, int d, int p)
  47. {
  48.     Queue *q = queue_new(d, p);
  49.  
  50.     while (*head && (*head)->priority < p) {
  51.         head = &(*head)->next;
  52.     }
  53.  
  54.     q->next = *head;
  55.     *head = q;
  56. }
  57.  
  58.  
  59. int queue_empty(Queue *head)
  60. {
  61.     return (head == NULL);
  62. }
  63.  
  64. void queue_print(const Queue *q)
  65. {
  66.     while (q) {
  67.         printf("%d[%d] ", q->data, q->priority);
  68.         q = q->next;
  69.     }
  70.  
  71.     puts("$");
  72. }
  73.  
  74. typedef struct Graph Graph;
  75. typedef struct Edge Edge;
  76.  
  77. struct Edge {
  78.     int vertex;
  79.     int weight;
  80.     Edge *next;
  81. };
  82.  
  83. struct Graph {
  84.     int v;
  85.     Edge **edge;
  86.     int *dist;
  87.     int *path;
  88. };
  89.  
  90. Graph *graph_new(int v)
  91. {
  92.     Graph *G = malloc(sizeof(*G));
  93.  
  94.     G->v = v;
  95.     G->edge = calloc(v, sizeof(*G->edge));
  96.     G->dist = calloc(v, sizeof(*G->dist));
  97.     G->path = calloc(v, sizeof(*G->path));
  98.  
  99.     return G;
  100. }
  101.  
  102. void graph_delete(Graph *G)
  103. {
  104.     if (G) {
  105.         for (int i = 0; i < G->v; i++) {
  106.             Edge *e = G->edge[i];
  107.  
  108.             while (e) {
  109.                 Edge *old = e;
  110.  
  111.                 e = e->next;
  112.                 free(old);
  113.             }
  114.         }
  115.  
  116.         free(G->edge);
  117.         free(G->dist);
  118.         free(G->path);
  119.         free(G);
  120.     }
  121. }
  122.  
  123. Edge *edge_new(int vertex, int weight, Edge *next)
  124. {
  125.     Edge *e = malloc(sizeof(*e));
  126.  
  127.     e->vertex = vertex;
  128.     e->weight = weight;
  129.     e->next = next;
  130.  
  131.     return e;
  132. }
  133.  
  134. void graph_edge(Graph *G, int u, int v, int w)
  135. {
  136.     G->edge[u] = edge_new(v, w, G->edge[u]);
  137.     G->edge[v] = edge_new(u, w, G->edge[v]);
  138. }
  139.  
  140. void dijkstra(const Graph *G, int s)
  141. {
  142.     Queue *queue = NULL;
  143.  
  144.     for (int i = 0; i < G->v; i++) G->dist[i] = -1;
  145.     G->dist[s] = 0;
  146.  
  147.     queue_push(&queue, s, 0);
  148.  
  149.     while (!queue_empty(queue)) {
  150.         int v = queue_pop(&queue);
  151.         Edge *e = G->edge[v];
  152.  
  153.         while (e) {
  154.             int w = e->vertex;
  155.             int d = G->dist[v] + e->weight;
  156.  
  157.             if (G->dist[w] == -1) {
  158.                 G->dist[w] = d;
  159.                 G->path[w] = v;
  160.  
  161.                 queue_push(&queue, w, d);                
  162.             } 
  163.  
  164.             if (G->dist[w] > d) {
  165.                 G->dist[w] = d;
  166.                 G->path[w] = v;
  167.  
  168.                 queue_remove(&queue, w);
  169.                 queue_push(&queue, w, d);
  170.             }
  171.  
  172.             e = e->next;
  173.         }
  174.     }
  175. }
  176.  
  177. int main()
  178. {
  179.     int t;
  180.  
  181.     scanf("%d", &t);
  182.  
  183.     while (t--) {
  184.         Graph *G;
  185.         int v, e, s;
  186.  
  187.         scanf("%d %d", &v, &e);
  188.  
  189.         G = graph_new(v);
  190.  
  191.         for (int i = 0; i < e; i++) {
  192.             int u, v, w;
  193.  
  194.             scanf("%d %d %d", &u, &v, &w);
  195.             graph_edge(G, u - 1, v - 1, w);
  196.         }
  197.  
  198.         scanf("%d", &s);
  199.         dijkstra(G, s - 1);
  200.  
  201.         for (int i = 0; i < G->v; i++) {
  202.             if (i != s - 1) {
  203.                 printf("%d ", G->dist[i]);
  204.             }
  205.         }
  206.  
  207.         puts("");
  208.         graph_delete(G);
  209.     }
  210.  
  211.     return 0;
  212. }
  213.  
Success #stdin #stdout 0s 9432KB
comments (?)
stdin 
2
5   4
1   2    5
2   3    6
3   4    2
1   3   15
1
4   4
1   2   24
1   4   20
3   1    3
4   3   12
1
stdout 
5 11 13 -1 
24 3 15
https://ideone.com/jnORk6
language:
C (gcc 8.3)
created:
7 years 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!