Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- typedef struct edge
- {
- struct edge *next;
- struct vertex *vertex;
- int distance;
- } t_edge;
- typedef struct vertex
- {
- t_edge* first;
- t_edge* last;
- int value;
- } t_vert;
- t_vert* createVertex(int value)
- {
- t_vert* new = malloc(sizeof(t_vert));
- new->first = NULL;
- new->last = NULL;
- new->value = value;
- return new;
- }
- int isempty(t_vert *vertex)
- {
- if(!vertex->first) return 1;
- return 0;
- }
- int equals(t_vert *vertexA, t_vert *vertexB)
- {
- if(vertexA->value == vertexB->value) return 1;
- return 0;
- }
- void createedge(t_vert* vertexA, t_vert* vertexB, int distance)
- {
- t_edge* edgeAB = malloc(sizeof(t_edge));
- edgeAB->vertex = vertexB;
- edgeAB->distance = distance;
- t_edge* edgeBA = malloc(sizeof(t_edge));
- edgeBA->vertex = vertexA;
- edgeBA->distance = distance;
- if(vertexA->first)
- {
- vertexA->last->next = edgeAB;
- vertexA->last = edgeAB;
- }
- else
- {
- vertexA->first = vertexA->last = edgeAB;
- }
- if(vertexB->first)
- {
- vertexB->last->next = edgeBA;
- vertexB->last = edgeBA;
- }
- else
- {
- vertexB->first = vertexB->last = edgeBA;
- }
- }
- int path(t_vert* before, t_vert *actual, t_vert *target)
- {
- if(equals(actual, target))
- {
- return 0;
- }
- if(!isempty(actual))
- {
- while(actual->first)
- {
- if(!equals(before, actual->first->vertex))
- {
- int val = path(actual, actual->first->vertex, target);
- if(val != -1)
- {
- return actual->first->distance + val;
- }
- }
- actual->first = actual->first->next;
- }
- }
- return -1;
- }
- int main()
- {
- int edgeCount, vertexCount, start, destination;
- int i;
- int temp;
- scanf("%d %d %d %d", &vertexCount, &edgeCount, &start, &destination);
- if(start > destination)
- {
- temp = destination;
- destination = start;
- start = temp;
- }
- t_vert **vertices;
- vertices = (t_vert **)malloc(sizeof(t_vert *) * vertexCount);
- for(i = 0; i < vertexCount; i++)
- {
- vertices[i] = createVertex(i);
- }
- for(i = 0; i < edgeCount; i++)
- {
- int vertexA, vertexB, length;
- scanf("%d %d %d", &vertexA, &vertexB, &length);
- createedge(vertices[vertexA-1], vertices[vertexB-1], length);
- }
- printf("%d\n", path(vertices[start-1], vertices[start-1], vertices[destination-1]));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement