#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;
}
Comments
0 B
|👍
/👎
0 B
|0 👍
/0 👎
0 B
|👍
/👎