Направленный граф: (не простой) путь с максимальным весом

Question

Ориентированный и взвешенный график сохраняется в файле через список его ребер в следующем формате: v1 val v2, где указывает, что v1 соединен с v2 ребром с весом val (int> 0).Это пример входного файла

fF 1 123
A0 2 fF
A0 5 h9
h9 3 123
123 2 F2
123 4 d1
F2 3 Dd
F2 4 d1
d1 2 Dd
d1 4 xd
d1 1 h9
Dd 5 xd
xd 4 A0
F2 3 fF

Я должен написать программу на C, которая:

1. читает файл и сохраняет график в соответствующей структуре данных
2. после получения двух вершин v1 и v2 и двух целых чисел k и p (k <= p) выведите путь, который начинается с <code>v1 и заканчивается на v2, что соответствует следующемуограничения
   • - это максимальная сумма весов
   • , которые пересекаются, по крайней мере, с k вершинами
   • общее количество повторных пересечений не меньше, чем p
   • путь заканчивается, когда он прибывает в конечную вершину

Я решил первую точку, но у меня нет представления о второй.Это весь код, который я написал:

main.c

#include <stdio.h>
#include <stdlib.h>
#include "graph.h"

void main() {
    int k = 1, p = 1;
    char v1[21], v2[21];
    graph_t G = GRAPHread("file.txt");
    printf("Insert 2 vertex");
    scanf("%s %s", v1, v2);
    GRAPHfindPath(G, k, p, v1, v2);
}

edge.h

#ifndef EDGE_H
#define EDGE_H

typedef struct edge_s { int v; int w; int wt; } edge_t;

edge_t EDGEcreate(int v, int w, int wt);

#endif

edge.c

#include "edge.h"

edge_t EDGEcreate(int v, int w, int wt) {
    edge_t e;
    e.v = v;
    e.w = w;
    e.wt = wt;
    return e;
}

ST.h

#ifndef ST_H
#define ST_H

typedef struct symbletable_s *st_t;

int STinsert(st_t st, char *key);
int STsearch(st_t st, char *k);
st_t STinit(int maxN);

#endif

ST.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ST.h"

struct symbletable_s { char **a; int M; };

st_t STinit(int maxN) {
    int i;
    st_t st = malloc(sizeof(*st));
    st->M = maxN;
    st->a = malloc(sizeof(char *)*st->M);
    return st;
}

int hash(char *k, int M) {
    int h = 0, base = 127;
    for (; *k != '\0'; k++) h = (base*h + *k) % M;
    return h;
}

int full(st_t st, int i) {
    if (st->a[i] == NULL) return 1;
    return 0;
}

int STinsert(st_t st, char *key) {
    int i = hash(key, st->M);
    while (full(st,i))
        i = (i + 1) % st->M;
    st->a[i] = malloc(sizeof(char)*(strlen(key) + 1));
    memcpy(st->a[i], key, strlen(key) + 1);
    return i;
}

int STsearch(st_t st, char *k) {
    int i = hash(k, st->M);
    while (full(st, i)) {
        if (strcmp(k, st->a[i]) == 0) return i;
        else i = (i + 1) % st->M;
    }
    return -1;
}

graph.h

#ifndef GRAPH_H
#define GRAPH_H

typedef struct graph_s *graph_t;

graph_t GRAPHread(char *s);
void GRAPHfindPath(graph_t G, int k, int p, char *v1, char *v2);


#endif

graph.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graph.h"
#include "ST.h"
#include "edge.h"

#define MAX 21

typedef struct node_s *link;
struct node_s { int v; int wt; link next; };

struct graph_s {
    int V;
    int E;
    link *adj_l;
    link z;
    st_t tab;
};

link NEW(int v, int wt, link next) {
    link x = malloc(sizeof *x);
    x->v = v;
    x->next = next;
    x->wt = wt;
    return x;
}

graph_t GRAPHinit(int V) {
    int v;
    graph_t G = malloc(sizeof *G);
    G->V = V; G->E = 0; G->z = NEW(-1, -1, NULL);
    G->adj_l = malloc(G->V*sizeof(link));
    for (v = 0; v < G->V; v++)
        G->adj_l[v] = G->z;
    G->tab = STinit(V);
    return G;
}

void insertE(graph_t G, edge_t e) {
    int v = e.v, w = e.w, wt = e.wt;
    G->adj_l[v] = NEW(w, wt, G->adj_l[v]);
    G->adj_l[w] = NEW(v, wt, G->adj_l[w]);
    G->E++;
}

graph_t GRAPHread(char *s) {
    graph_t G;
    char src[MAX], dst[MAX];
    char v1[MAX], v2[MAX];
    int nE = 0, i, i1, i2, wt;
    FILE *fp = fopen(s, "r");
    while (fscanf(fp, "%*s %*d %*s") != EOF)
        nE++;
    rewind(fp);
    G = GRAPHinit(nE * 2);
    for (i = 0; i < nE; i++) {
        fscanf(fp, "%s %d %s", src, &wt, dst);
        i1 = STinsert(G->tab, src);
        i2 = STinsert(G->tab, dst);
        insertE(G, EDGEcreate(i1, i2, wt));
    }
    fclose(fp);
    return G;
}

void GRAPHfindPath(graph_t G, int k, int p, char *v1, char *v2) {

}