Created
May 10, 2014 19:58
-
-
Save Rag0n/e7f6403a7fca98b841b4 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // | |
| // main.c | |
| // connected components | |
| // | |
| // Created by Александр on 08.05.2557 BE. | |
| // Copyright (c) 2557 Alexander Guschin. All rights reserved. | |
| // | |
| #include <stdio.h> | |
| #include <string.h> | |
| #include <stdlib.h> | |
| #define MAXVALUE 100000 | |
| int *visited, *heap, *prev, *dist; | |
| int size = 0; | |
| struct vertex { | |
| int key; // вершина графа | |
| int lenght; | |
| struct vertex *next; | |
| }; | |
| void swap(int one, int two) | |
| { | |
| int temp = heap[one]; | |
| heap[one] = heap[two]; | |
| heap[two] = temp; | |
| } | |
| void heapify(int pos) | |
| { | |
| int left = pos*2 + 1, right = pos*2 + 2; | |
| int largest = pos; | |
| if (left < size && dist[heap[left]] < dist[heap[largest]]) | |
| { | |
| largest = left; | |
| } | |
| if (right < size && dist[heap[right]] < dist[heap[largest]]) | |
| { | |
| largest = right; | |
| } | |
| if (largest != pos) | |
| { | |
| swap(pos, largest); | |
| heapify(largest); | |
| } | |
| } | |
| void insert(int value) | |
| { | |
| int pos = size, parent; | |
| heap[size] = value; | |
| size++; | |
| while(pos) | |
| { | |
| parent = (pos-1)/2; | |
| if (dist[heap[pos]] < dist[heap[parent]]) | |
| { | |
| swap(pos, parent); | |
| pos = (pos-1)/2; | |
| } | |
| else | |
| break; | |
| } | |
| } | |
| int pop() | |
| { | |
| int num = heap[0]; | |
| swap(0, size-1); | |
| size--; | |
| heapify(0); | |
| return num; | |
| } | |
| void printGraph(struct vertex *graph, int n) | |
| { | |
| struct vertex *pntVertex; | |
| printf("Graph:\n"); | |
| for (int i = 1; i < n; i++) { | |
| printf("%d:", graph[i].key); | |
| pntVertex = graph[i].next; | |
| while (pntVertex != NULL) { | |
| printf(" %d(%d)", pntVertex->key, pntVertex->lenght); | |
| pntVertex = pntVertex->next; | |
| } | |
| printf("\n"); | |
| } | |
| } | |
| void initGraph(int n, struct vertex *graph) | |
| { | |
| for (int i = 1; i < n; i++) { | |
| graph[i].key = i; | |
| } | |
| } | |
| void addEdge(int x, int y, int l, struct vertex *graph) | |
| { | |
| struct vertex *newVertex; | |
| newVertex = (struct vertex*)malloc(sizeof(struct vertex)); | |
| newVertex->key = y; | |
| newVertex->lenght = l; | |
| newVertex->next = graph[x].next; | |
| graph[x].next = newVertex; | |
| } | |
| void dijkstra(struct vertex *graph, int vertex, int n) | |
| { | |
| struct vertex *pnt; | |
| int u; | |
| for (int i = 1; i < n; i++) { | |
| dist[i] = MAXVALUE; | |
| prev[i] = -1; | |
| } | |
| dist[vertex] = 0; // начало | |
| for (int i = 1; i < n; i++) { | |
| insert(graph[i].key); | |
| // insert(i); | |
| } | |
| while (size) { | |
| u = pop(); | |
| pnt = graph[u].next; | |
| while (pnt != NULL) { // просматриваем все смежные | |
| // и релаксируем ребра | |
| if (dist[pnt->key] > dist[u] + pnt->lenght) { | |
| dist[pnt->key] = dist[u] + pnt->lenght; | |
| prev[pnt->key] = u; | |
| heapify(0); // меняем приоритет в очереди | |
| } | |
| pnt = pnt->next; | |
| } | |
| } | |
| } | |
| int main(int argc, const char * argv[]) | |
| { | |
| int n, m, x, y, u, v, l; | |
| struct vertex *graph; | |
| scanf("%d", &n); // вершины | |
| scanf("%d", &m); // ребра | |
| n++; | |
| graph = (struct vertex*)calloc(n, sizeof(struct vertex)); | |
| initGraph(n, graph); | |
| for (int i = 0; i < m; i++) { | |
| scanf("%d", &x); | |
| scanf("%d", &y); | |
| scanf("%d", &l); | |
| addEdge(x, y, l, graph); | |
| } | |
| scanf("%d", &u); // путь от u | |
| scanf("%d", &v); // до v | |
| prev = (int *)calloc(n, sizeof(int)); | |
| dist = (int *)calloc(n, sizeof(int)); | |
| heap = (int *)calloc(n, sizeof(int)); | |
| dijkstra(graph, u, n); | |
| // printGraph(graph, n); | |
| if (dist[v] != MAXVALUE) { | |
| printf("%d\n", dist[v]); | |
| } | |
| else | |
| printf("%d\n", -1); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment