-
Notifications
You must be signed in to change notification settings - Fork 4
/
longest-path.c
80 lines (68 loc) 路 1.7 KB
/
longest-path.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include "../../../data-structures/linked-list/linked-list.h"
#include <stdio.h>
#include <stdlib.h>
int infinity = -1000000;
int V, E, from, target;
int **weight;
int *dp;
int *n;
linked_list **graph;
int max(int a, int b) { return a <= b ? b : a; }
int longest_path_from(int u) {
if (u == target)
return 0;
if (dp[u] != infinity)
return dp[u];
linked_list *children = graph[u];
linked_list_node *child = children->nil->next;
int w;
while (child != children->nil) {
w = child->key;
if (weight[u][w] + longest_path_from(w) > dp[u]) {
dp[u] = weight[u][w] + longest_path_from(w);
n[u] = w;
}
child = child->next;
}
return dp[u];
}
void print_longest_path(int u) {
if (u == target) {
printf("%d", target);
return;
}
printf("%d -> ", u);
print_longest_path(n[u]);
}
int main() {
scanf("%d %d %d %d", &V, &E, &from, &target);
int i, j, u, v, w;
graph = malloc(sizeof(linked_list *) * (V + 1));
weight = (int **)malloc(sizeof(int *) * (V + 1));
dp = (int *)malloc(sizeof(int) * (V + 1));
n = (int *)malloc(sizeof(int) * (V + 1));
for (i = 0; i <= V; i++) {
graph[i] = AllocateLinkedList();
weight[i] = (int *)malloc(sizeof(int) * (V + 1));
dp[i] = infinity;
}
for (i = 0; i <= E; i++) {
scanf("%d %d %d", &u, &v, &w);
weight[u][v] = w;
ListInsert(graph[u], v);
}
int path = longest_path_from(from);
printf("longest path %d -> %d cost is: %d\n", from, target, path);
printf("longest path %d -> %d is: ", from, target);
print_longest_path(from);
printf("\n");
for (i = 0; i <= V; i++) {
DellocateLinkedList(graph[i]);
free(weight[i]);
}
free(dp);
free(n);
free(graph);
free(weight);
return 0;
}