/*
Time limit: 1500ms
Memory limit: 256mb
---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// this linked list has no head or tail, which means that if this list is empty, then it equals NULL
struct linkedListNode {
int id;
int weight; // you can maintain the weight of the edge in the linked list node if you need to
struct linkedListNode* next;
};
typedef struct linkedListNode* ListNode;
ListNode CreateNode(int id) {
ListNode node = (ListNode) malloc(sizeof(struct linkedListNode));
node->id = id;
node->next = NULL;
return node;
}
// Queue ADT
struct queueNode {
int id; // each node in the Queue contains an ID
struct queueNode* next;
struct queueNode* prev;
};
typedef struct queueNode* QueueNode;
struct queue {
int capacity;
QueueNode head;
QueueNode tail;
int size;
};
typedef struct queue* QueueADT;
QueueNode AllocateEmptyQueueNode() {
QueueNode newNode = (QueueNode) malloc(sizeof(struct queueNode));
newNode->id = -1;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
QueueADT CreateQueue(int capacity) {
QueueADT q = (QueueADT) malloc(sizeof(struct queue));
q->capacity = capacity;
q->size = 0;
q->head = AllocateEmptyQueueNode();
q->tail = AllocateEmptyQueueNode();
q->head->next = q->tail;
q->tail->prev = q->head;
return q;
}
int IsEmpty(QueueADT q) {
return q->size == 0;
}
int IsFull(QueueADT q) {
return q->size == q->capacity;
}
void Enqueue(QueueADT q, int id) {
if (q->size < q->capacity) {
QueueNode tmp = AllocateEmptyQueueNode();
tmp->id = id;
QueueNode prev = q->tail->prev;
prev->next = tmp;
tmp->prev = prev;
tmp->next = q->tail;
q->tail->prev = tmp;
q->size++;
}
}
int Dequeue(QueueADT q) {
if (!IsEmpty(q)) {
q->size--;
int v;
QueueNode tmp = q->head->next;
q->head->next = tmp->next;
tmp->next->prev = q->head;
v = tmp->id;
free(tmp);
return v;
} else {
return -1;
}
}
void FreeQueue(QueueADT q) {
QueueNode tmp = q->head;
while (tmp != NULL) {
QueueNode next = tmp->next;
free(tmp);
tmp = next;
}
free(q);
}
// graph
// For example, G[i] is exactly the adjacency list of the node i
struct graph {
int n;
ListNode* G;
};
typedef struct graph* GraphADT;
GraphADT CreateGraph(int n) {
GraphADT myGraph = (GraphADT) malloc(sizeof(struct graph));
myGraph->n = n;
myGraph->G = (ListNode*) malloc(n * sizeof(ListNode));
memset(myGraph->G, 0, n * sizeof(ListNode));
return myGraph;
}
// Add an edge (u, v) with weight w to the graph myGraph.
// Note that the graph is undirected, which means that you also need to add an edge (v, u) with weight w to the graph myGraph.
// You can maintain the weight of the edge in the linked list node if you need to.
// Use 'void AddEdge(GraphADT myGraph, int u, int v, int w)' if you need to maintain the weight of the edge.
void AddEdge(GraphADT myGraph, int u, int v, int w) {
// WRITE YOUR CODE HERE
}
int max(int a, int b) {
return a > b ? a : b;
}
// Compute the minimum distance from S to T in the graph myGraph, and return the answer.
// If there is no path from S to T, return -1.
int Query(GraphADT myGraph, int S, int T, int K, int *a) {
if (S == T) {
return 0;
}
// Remember to free the memory of the queue and the distance array before returning the answer
// WRITE YOUR CODE HERE
}
int main()
{
int n, m, K, S, T;
scanf("%d%d%d%d%d", &n, &m, &K, &S, &T);
int *a = (int*) malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
GraphADT myGraph = CreateGraph(n);
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
AddEdge(myGraph, u, v, w);
AddEdge(myGraph, v, u, w);
}
int ans = Query(myGraph, S, T, K, a);
printf("%d\n", ans);
return 0;
}
---------------------------------------End of Code---------------------------------------
## Minimum Length with Constraints (Bonus)
You are supposed to solve this problem by implementing Graph ADT and BFS.
You are given an undirected graph with $n$ nodes and $m$ weighted edges. You start at node $S$ and your destination is node $T$.
You begin at node $S$ with $K$ units of energy. To traverse an edge with weight $w$, you must have at least $w$ units of energy (current energy $\ge w$). After passing the edge, your energy decreases by $w$. Each node $i$ has a recharge value $a_i$. Upon arriving at node $i$, if your current energy is less than $a_i$, it is automatically increased to $a_i$. If your current energy is already greater than or equal to $a_i$, it remains unchanged.
The length of every edge is considered 1 unit. Calculate the minimum length (total number of edges) required to travel from $S$ to $T$. If $T$ is not reachable from $S$, output -1.
Hint: Beware of memory limits. An O(m * K) space approach will fail with a 'Judge Error' due to memory limits. You are supposed to use an approach within O(n * K + m) space.
### Input
First line contains five integers $n, m, K, S$ and $T$ ($1 \leq n \leq 10^5, m \leq 5*10^5, 1 \leq K \leq 50, 0 \leq S, T < n$).
The next $n$ lines each contain one integer $a_i$ ($0 \leq a_i \leq K$), representing the recharge value for node $i$ (where $i$ is from $0$ to $n-1$).
The next $m$ lines each contain three integers $u, v, w$: representing an undirected edge between nodes $u$ and $v$ with an energy cost $w$ ($0 \leq u, v < n, u \neq v, 0 \leq w \leq K$).
### Output
Output a single integer representing the minimum length from $S$ to $T$.
Output -1 if $T$ is not reachable from $S$.
### Example
**Input 1**
4 4 10 0 3
5
2
8
0
0 1 6
1 2 4
0 2 10
2 3 7
**Output 1**
2
**Input 2**
4 4 10 1 3
5
2
8
0
0 1 6
1 2 4
0 2 10
2 3 9
**Output 2**
-1
**Explanation**
The path with minimum length 2 in example 1 is: 0 -> 2 -> 3.