3_1.c

#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;
}