Time limit: 35ms
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 <stdbool.h>
#include <limits.h>
#define MAX_DISTANCE 999999
#define MAX_NODES 1000
#define CAPACITY 4000
// min heap
struct node {
int id;
int dis;
};
typedef struct node* Node;
struct Heap {
int capacity;
int size;
Node* arr;
};
typedef struct Heap* HeapADT;
Node CreateNode(int id, int dis) {
Node tmp = (Node) malloc(sizeof(struct node));
tmp->id = id;
tmp->dis = dis;
return tmp;
}
HeapADT CreateHeap(int capacity) {
HeapADT heap = (HeapADT) malloc(sizeof(struct Heap));
heap->capacity = capacity;
heap->size = 0;
heap->arr = (Node*) malloc((capacity + 1) * sizeof(struct node));
return heap;
}
void InsertHeap(HeapADT heap, Node tmp) {
if (heap->size < heap->capacity) {
heap->size++;
int cur = heap->size;
int father = cur / 2;
while (father >= 1 && heap->arr[father]->dis > tmp->dis) {
heap->arr[cur] = heap->arr[father];
cur = father;
father = cur / 2;
}
heap->arr[cur] = tmp;
}
}
void DeleteHeap(HeapADT heap) {
if (heap->size != 0) {
Node tmp = heap->arr[heap->size];
heap->size--;
int cur = 1;
int child = cur * 2;
while (child <= heap->size) {
if (child + 1 <= heap->size && heap->arr[child+1]->dis < heap->arr[child]->dis) {
child++;
}
if (heap->arr[child]->dis < tmp->dis) {
heap->arr[cur] = heap->arr[child];
cur = child;
child = cur * 2;
} else {
break;
}
}
heap->arr[cur] = tmp;
}
}
Node Top(HeapADT heap) {
if (heap->size > 0) {
return heap->arr[1];
} else {
return NULL;
}
}
int Empty(HeapADT heap) {
if (heap->size > 0) {
return 0;
} else {
return 1;
}
}
// graph related data structure
struct edgeNode {
int v;
int weight;
};
typedef struct edgeNode Edge;
// the maximum number of nodes is known as MAX_NODES
// we use array to store every edge, represented by Edge
// For example, graph[1][2] is the third neighbor of the node 1. Its id is graph[1][2].v and its edge weight is graph[1][2].weight
// we use edgeNum to record the number of neighbors of each node
// For example, edgeNum[1] is the number of edges of the node 1
Edge graph[MAX_NODES][MAX_NODES];
int edgeNum[MAX_NODES];
int dist[MAX_NODES];
int color[MAX_NODES];
HeapADT myHeap; // min heap
// Tips: use the HeapADT & Try to stop early
int CloseNeighbor(int src, int n, int k) {
// write down your code here
}
void Reset() {
for (int i = 0; i < MAX_NODES; i++) {
dist[i] = MAX_DISTANCE;
color[i] = 0;
}
myHeap->size = 0;
}
int main() {
for (int i = 0; i < MAX_NODES; i++) {
edgeNum[i] = 0;
}
myHeap = CreateHeap(CAPACITY);
int n, m, src, k;
scanf("%d%d%d",&n, &m, &k);
int x, y, w;
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &x, &y, &w);
graph[x][edgeNum[x]].v = y;
graph[x][edgeNum[x]++].weight = w;
graph[y][edgeNum[y]].v = x;
graph[y][edgeNum[y]++].weight = w;
}
int num;
scanf("%d", &num);
for (int i=0;i<num;++i) {
scanf("%d", &src);
Reset();
printf("%d\n", CloseNeighbor(src, n, k));
}
return 0;
}
-----------------------------------------End of Code-----------------------------------------
Description:
Given an undirected weighted graph, a source node s, a distance threshold k, report the number of its close neighbors.
If a node u is the close neighbor of s, then the shortest path distance between u and s is no larger than k.
The close neighbors do not include the source node itself.
Note that your algorithm must run in O((m+n)*log(n)) time.
Besides, please remove any redundant part of your codes and try to make it more efficient.
In addition, can you figure out a way to stop early instead of directly calculating the distance between the source node and every other node?
If your algorithm does not meet the above conditions, you may get "Out Of Time".
Input:
The first line contains three integer: n, m, k, which are the number of nodes, the number of edges, and the distance threshold, respectively.
The next m lines, each of which contains three integer: u, v, w, where u and v are the node of the edge, and w is the edge weight.
The next one line contains one integer: num, which are the number of source nodes
The next num lines, each of which contains one integer, which is the source node
Output:
For each source node, print the number of the close neighbors of the source node under the distance threshold.
Sample Input 1:
7 8 3
1 0 4
1 2 1
1 3 5
1 4 4
1 5 4
2 3 1
3 4 1
3 6 2
1
1
Sample Output 1:
3