单源无权图的最短路径算法

本博客的代码的思想和图片参考：好大学慕课浙江大学陈越老师、何钦铭老师的《数据结构》

算法思想：按照递增(非递减)的顺序找出到各个顶点的最短路径。程序的框架和BFS有点类似

下面是代码演示：

  1 /*
  2  * singleUnweight.c
  3  *
  4  *  Created on: 2017年5月13日
  5  *      Author: ygh
  6  */
  7 
  8 #include <stdio.h>
  9 #include <stdlib.h>
 10 
 11 /*
 12  * Algorithm thought:
 13  * We easily know this question is BFS.
 14  * we  access the first level nodes, then access second level nodes
 15  * until we reach the sixth level.
 16  * We let every node to BFS until it reach the sixth level,then we record the total nodes M
 17  * it can reach, calculate the M/N(The total point the test data gives) .
 18  */
 19 
 20 #define MAX_VERTEX_MUM 10001
 21 typedef int vertex; /*vertex is the index of point in the graph*/
 22 typedef int dataType; /*dataType is the data type of vertex */
 23 typedef int weightType; /*The data type of weight  */
 24 
 25 /*
 26  * Define a data structure to edge
 27  */
 28 typedef struct eNode *ptrToENode;
 29 typedef struct eNode {
 30     vertex v1, v2;
 31     weightType wight;
 32 };
 33 typedef ptrToENode edge;
 34 
 35 /*
 36  * Define a data structure for adjacent table node
 37  */
 38 typedef struct adjNode *ptrToAdjNode;
 39 typedef struct adjNode {
 40     vertex adjVertex; /*The index of vertex in the graph*/
 41     weightType weight; /*the value of the weight*/
 42     ptrToAdjNode next; /*A point to point next node*/
 43 };
 44 
 45 /*
 46  * Define a data structure for adjacent table head point
 47  */
 48 typedef struct vNode *ptrToVNode;
 49 typedef struct vNode {
 50     dataType data; /*The value of every vertex,some times it will be ignore*/
 51     ptrToAdjNode head;/*The point to point the adjacent table first element*/
 52 } adjList[MAX_VERTEX_MUM];
 53 
 54 /*Define a data structure for graph*/
 55 typedef struct gNode *ptrToGNode;
 56 typedef struct gNode {
 57     int vertex_num;
 58     int edge_num;
 59     adjList g;
 60 };
 61 typedef ptrToGNode adjacentTableGraph; /*a graph show by adjacent table*/
 62 
 63 /*
 64  create a graph given the vertex number.
 65  @param vertexNum The verter number of the graph
 66  @return a graph with vertex but no any egdgs
 67  */
 68 ptrToGNode createGraph(int vertexNum) {
 69     vertex v;
 70     adjacentTableGraph graph = (adjacentTableGraph) malloc(
 71             sizeof(struct gNode));
 72     graph->vertex_num = vertexNum;
 73     graph->edge_num = 0;
 74     for (v = 1; v <= graph->vertex_num; v++) {
 75         graph->g[v].head = NULL;
 76     }
 77     return graph;
 78 }
 79 
 80 /*
 81  insert a edge to graph.We will distinct oriented graph and undirected graph
 82  The e->v1 and e->v2 are the vertexs' indexs in the adjacent table
 83  @param graph The graph you want to insert edge
 84  @param e The edge you want to insert the graph
 85  @param isOriented Whether the graph is oriented graph.If the graph is oriented
 86  we will set adjacent table graph[v1]->head=v2 and set graph[v1].head=v2
 87  otherwise we only set graph[v1].head=v2
 88  */
 89 void insertEdge(adjacentTableGraph graph, edge e, int isOriented) {
 90     ptrToAdjNode newNode;
 91     newNode = (ptrToAdjNode) malloc(sizeof(struct adjNode));
 92     newNode->adjVertex = e->v2;
 93     newNode->weight = e->wight;
 94     newNode->next = graph->g[e->v1].head;
 95     graph->g[e->v1].head = newNode;
 96     if (!isOriented) {
 97         newNode = (ptrToAdjNode) malloc(sizeof(struct adjNode));
 98         newNode->adjVertex = e->v1;
 99         newNode->weight = e->wight;
100         newNode->next = graph->g[e->v2].head;
101         graph->g[e->v2].head = newNode;
102     }
103 }
104 
105 adjacentTableGraph buildGraph(int isordered) {
106     adjacentTableGraph graph;
107     edge e;
108     vertex v;
109     int vertex_num;
110     scanf("%d", &vertex_num);
111     graph = createGraph(vertex_num);
112     scanf("%d", &(graph->edge_num));
113     if (graph->edge_num) {
114         e = (edge) malloc(sizeof(struct eNode));
115         for (v = 0; v < graph->edge_num; v++) {
116             scanf("%d %d", &e->v1, &e->v2);
117             e->v1--;
118             e->v2--;
119             e->wight = 1;
120             insertEdge(graph, e, isordered);
121         }
122     }
123     return graph;
124 }
125 
126 /*==============================define a queue=====================================================*/
127 /*define a list to store the element in the queue*/
128 typedef vertex elementType;
129 typedef struct node *pList;
130 typedef struct node {
131     elementType element;
132     struct node *next;
133 };
134 
135 /*define a queue to point the list*/
136 typedef struct node2 *pQueue;
137 typedef struct node2 {
138     pList front; /*the front point to point the head of the list*/
139     pList rear; /*the rear point to point the rear of of the list*/
140 };
141 
142 /*create a empty list to store the queue element*/
143 pList createEmptyList() {
144     pList list;
145     list = (pList) malloc(sizeof(struct node));
146     list->next = NULL;
147     return list;
148 }
149 /*create a empty queye*/
150 pQueue createEmptyQueue() {
151     pQueue queue = (pQueue) malloc(sizeof(struct node2));
152     queue->front = NULL;
153     queue->rear = NULL;
154     return queue;
155 }
156 
157 /*
158  Wether the queue is empty
159  @param queue The queue need to adjust
160  @return If the queue is null,return 1 otherwise return 0
161  */
162 int isQueueEmpty(pQueue queue) {
163     return (queue->front == NULL);
164 }
165 
166 /*
167  Add a element to a queue,If the queue is null,we will create a new queue
168  @parama queue The queue we will add elememt to
169  @prama element The element we will add to queue
170  */
171 void addQueue(pQueue queue, elementType element) {
172     if (isQueueEmpty(queue)) {
173         pList list = createEmptyList();
174         list->element = element;
175         queue->front = queue->rear = list;
176     } else {
177         pList newNode = (pList) malloc(sizeof(struct node));
178         newNode->element = element;
179         newNode->next = queue->rear->next;
180         queue->rear->next = newNode;
181         queue->rear = newNode;
182     }
183 }
184 
185 /*
186  delete a element from a queue
187  @param queue The queue will be deleted a element
188  @return The element has been deleted
189  */
190 elementType deleteEleFromQueue(pQueue queue) {
191     if (isQueueEmpty(queue)) {
192         printf("the queue is empty,don't allow to delete elemet from it!");
193         return -1;
194     } else {
195         pList oldNode = queue->front;
196         elementType element = oldNode->element;
197         if (queue->front == queue->rear) {
198             queue->rear = queue->front = NULL;
199         } else {
200             queue->front = queue->front->next;
201         }
202         free(oldNode);
203         return element;
204     }
205 }
206 
207 
208 void unWeight(adjacentTableGraph graph, int *dist, int *path, vertex startPoint) {
209     dist[startPoint] = 0;
210     vertex v;
211     ptrToAdjNode w;
212     pQueue queue = createEmptyQueue();
213     addQueue(queue, startPoint);
214     while (!isQueueEmpty(queue)) {
215         v = deleteEleFromQueue(queue);
216         for (w = graph->g[v].head; w; w = w->next) {
217             if (dist[w->adjVertex] == -1) {
218                 addQueue(queue, w->adjVertex);
219                 dist[w->adjVertex] = dist[v] + 1;
220                 path[w->adjVertex] = v;
221             }
222         }
223     }
224 }
225 
226 /*
227  * Fill a array with value
228  * @param arr The array need to be filled
229  * @param length The length of the array
230  * @param filledValue The value the array will be filled
231  */
232 void fullArray(int *arr, int length, int filledValue) {
233     int i;
234     for (i = 0; i < length; i++) {
235         arr[i] = filledValue;
236     }
237 }
238 
239 /*============================define a stack to print result=============*/
240 typedef int stackElement;
241 typedef struct node3 {
242     stackElement element;
243     struct node3 *next;
244 } sta, *pStack;
245 
246 pStack createEmptyStack() {
247     pStack stack;
248     stack = (pStack) malloc(sizeof(sta));
249     if (stack) {
250         stack->next = NULL;
251     }
252     return stack;
253 }
254 
255 int isEmpty(pStack stack) {
256     if (stack->next == NULL) {
257         return 1;
258     } else {
259         return 0;
260     }
261 }
262 
263 void push(pStack stack, stackElement element) {
264     pStack node = (pStack) malloc(sizeof(sta));
265     node->element = element;
266     node->next = stack->next;
267     stack->next = node;
268 }
269 
270 stackElement pop(pStack stack) {
271     stackElement element;
272     pStack topHead;
273     if (isEmpty(stack)) {
274         printf("the stack is empty,can not pop");
275         return -65536;
276     } else {
277         topHead = stack->next;
278         stack->next = topHead->next;
279         element = topHead->element;
280         free(topHead);
281         return element;
282     }
283 }
284 
285 void findPath(int *path, int length, int destination) {
286     pStack stack = createEmptyStack();
287     vertex v;
288     int index = destination;
289     push(stack, index);
290     while (v != -1) {
291         v = path[index];
292         push(stack, v);
293         index = v;
294     }
295 
296     pop(stack);
297     while (!isEmpty(stack)) {
298         stackElement element = pop(stack);
299         printf("%d ", element+1);
300     }
301 }
302 
303 int main() {
304     adjacentTableGraph graph = buildGraph(1);
305     int dist[graph->vertex_num];
306     int path[graph->vertex_num];
307     fullArray(dist, graph->vertex_num, -1);
308     fullArray(path, graph->vertex_num, -1);
309     unWeight(graph, dist, path, 2);
310     findPath(path, graph->vertex_num, 6);
311     printf("just test");
312     return 0;
313 }

singleUnweight

下面使用一道算法题目来说明：

This time let us consider the situation in the movie "Live and Let Die" in which James Bond, the world's most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape -- he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head... Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).

Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him a shortest path to reach one of the banks. The length of a path is the number of jumps that James has to make.

Input Specification:

Each input file contains one test case. Each case starts with a line containing two positive integers

Output Specification:

For each test case, if James can escape, output in one line the minimum number of jumps he must make. Then starting from the next line, output the position

Sample Input 1:

Sample Output 1:

Sample Input 2:

Sample Output 2:

  1 /*
  2  * save.c
  3  *
  4  *  Created on: 2017年5月13日
  5  *      Author: ygh
  6  */
  7 #include <stdio.h>
  8 #include <stdlib.h>
  9 #include <math.h>
 10 
 11 /*
 12  * Algorithm thoughts:
 13  * we see every crocodile as a point in graph,and we use BFS or DFS to
 14  * search the path the James can reach river bank.
 15  * In this question,we store graph use a array,not the standard graph,because
 16  * in this question, the point in graph is not only crocodies but also the river band
 17  * how to show them by a graph. So we give up use traditional graph to show them
 18  * and use a array to show them.
 19  * But how to judge the adjacent point. we use this point as the central,use the max
 20  * jump distance as the radius, that which points in this circle is this
 21  * point's adjacent point.
 22  *
 23  * We write the program of BFS and DFS,you can choose one of them of run the program.
 24  */
 25 
 26 #define MAX_LENGTH 100
 27 
 28 typedef int vertex;
 29 
 30 /*
 31  * Define a data structure to store a point
 32  */
 33 typedef int node1Element;
 34 typedef struct node1 {
 35     node1Element x; /*The x-coordinate of the point*/
 36     node1Element y; /*The y-coordinate of the point*/
 37 } point[MAX_LENGTH];
 38 
 39 /*
 40  * Define a data structure to store a graph
 41  */
 42 typedef struct node2 *pGraph;
 43 typedef struct node2 {
 44     int vertex_num; /*The quantity of the all points*/
 45     int maxDistance; /*The max distance the James can jump*/
 46     point collection; /*A structure array to store the points*/
 47 };
 48 
 49 /*
 50  * Build a graph by a list of points
 51  */
 52 pGraph buildGraph() {
 53     int vertexMum, distance, i;
 54     vertex x, y;
 55     scanf("%d", &vertexMum);
 56     scanf("%d", &distance);
 57     pGraph graph = (pGraph) malloc(sizeof(struct node2));
 58     graph->vertex_num = vertexMum;
 59     graph->maxDistance = distance;
 60     if (graph->maxDistance) {
 61         for (i = 0; i < graph->vertex_num; i++) {
 62             scanf("%d %d", &x, &y);
 63             graph->collection[i].x = x;
 64             graph->collection[i].y = y;
 65         }
 66     }
 67     return graph;
 68 }
 69 
 70 /*==============================define a queue=====================================================*/
 71 /*define a list to store the element in the queue*/
 72 typedef vertex elementType;
 73 typedef struct node3 *pList;
 74 typedef struct node3 {
 75     elementType element;
 76     struct node3 *next;
 77 };
 78 
 79 /*define a queue to point the list*/
 80 typedef struct node4 *pQueue;
 81 typedef struct node4 {
 82     pList front; /*the front point to point the head of the list*/
 83     pList rear; /*the rear point to point the rear of of the list*/
 84 };
 85 
 86 /*create a empty list to store the queue element*/
 87 pList createEmptyList() {
 88     pList list;
 89     list = (pList) malloc(sizeof(struct node3));
 90     list->next = NULL;
 91     return list;
 92 }
 93 /*create a empty queye*/
 94 pQueue createEmptyQueue() {
 95     pQueue queue = (pQueue) malloc(sizeof(struct node4));
 96     queue->front = NULL;
 97     queue->rear = NULL;
 98     return queue;
 99 }
100 
101 /*
102  Wether the queue is empty
103  @param queue The queue need to adjust
104  @return If the queue is null,return 1 otherwise return 0
105  */
106 int isQueueEmpty(pQueue queue) {
107     return (queue->front == NULL);
108 }
109 
110 /*
111  Add a element to a queue,If the queue is null,we will create a new queue
112  @parama queue The queue we will add elememt to
113  @prama element The element we will add to queue
114  */
115 void addQueue(pQueue queue, elementType element) {
116     if (isQueueEmpty(queue)) {
117         pList list = createEmptyList();
118         list->element = element;
119         queue->front = queue->rear = list;
120     } else {
121         pList newNode = (pList) malloc(sizeof(struct node3));
122         newNode->element = element;
123         newNode->next = queue->rear->next;
124         queue->rear->next = newNode;
125         queue->rear = newNode;
126     }
127 }
128 
129 /*
130  delete a element from a queue
131  @param queue The queue will be deleted a element
132  @return The element has been deleted
133  */
134 elementType deleteEleFromQueue(pQueue queue) {
135     if (isQueueEmpty(queue)) {
136         printf("the queue is empty,don't allow to delete elemet from it!");
137         return -1;
138     } else {
139         pList oldNode = queue->front;
140         elementType element = oldNode->element;
141         if (queue->front == queue->rear) {
142             queue->rear = queue->front = NULL;
143         } else {
144             queue->front = queue->front->next;
145         }
146         free(oldNode);
147         return element;
148     }
149 }
150 
151 /*
152  * Calculate the distance from point to safe place
153  * @param x The x-coordinate of the point
154  * @param y THe y-coordinate of the point
155  * @param xLine The x base line of square
156  * @param yLine The y base line of the square
157  */
158 int calculateDtoSafe(int x, int y, int xLine, int yLine) {
159     int distanceX, distanceY;
160     distanceX = abs(x - xLine);
161     distanceY = abs(y - yLine);
162     return (distanceX > distanceY ? distanceY : distanceX);
163 }
164 
165 /**
166  * Calculate two points distance
167  * @return The float distance of twp points
168  */
169 float calculateTwoPointDistance(int x1, int y1, int x2, int y2) {
170     return (sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
171 }
172 
173 /*
174  * Judge the point that whether the James Bond can jump into river bank
175  * @param graph A graph to stored all points' collection
176  * @param point The index of point in the points' collection
177  * @return 1 will be return if James Bond can jump into river bank, otherwise
178  * return 0
179  */
180 int isSafe(pGraph graph, vertex point) {
181     int x, y, distance;
182     x = graph->collection[point].x;
183     y = graph->collection[point].y;
184     if (x >= 0 && y >= 0) {
185         distance = calculateDtoSafe(x, y, 50, 50);
186     }
187     if (x >= 0 && y <= 0) {
188         distance = calculateDtoSafe(x, y, 50, -50);
189     }
190 
191     if (x <= 0 && y >= 0) {
192         distance = calculateDtoSafe(x, y, -50, 50);
193     }
194 
195     if (x <= 0 && y <= 0) {
196         distance = calculateDtoSafe(x, y, -50, -50);
197     }
198 
199     if (distance <= graph->maxDistance) {
200         return 1;
201     } else {
202         return 0;
203     }
204 }
205 
206 /*
207  * Judge the point that whether the James Bond can jump into river bank
208  * @param graph A graph to stored all points' collection
209  * @param point The index of point in the points' collection
210  * @return 1 will be return if James Bond can jump into river bank, otherwise
211  * return 0
212  */
213 int getLastDistance(pGraph graph, vertex point) {
214     int x, y, distance = 0;
215     x = graph->collection[point].x;
216     y = graph->collection[point].y;
217     if (x > 0 && y > 0) {
218         distance = calculateDtoSafe(x, y, 50, 50);
219     }
220     if (x > 0 && y < 0) {
221         distance = calculateDtoSafe(x, y, 50, -50);
222     }
223 
224     if (x < 0 && y > 0) {
225         distance = calculateDtoSafe(x, y, -50, 50);
226     }
227 
228     if (x < 0 && y < 0) {
229         distance = calculateDtoSafe(x, y, -50, -50);
230     }
231 
232     return distance;
233 }
234 
235 /*
236  * Whether the James can jump over from source to destination
237  */
238 int isJump(pGraph graph, vertex source, vertex destination) {
239     if (calculateTwoPointDistance(graph->collection[source].x,
240             graph->collection[source].y, graph->collection[destination].x,
241             graph->collection[destination].y) > graph->maxDistance) {
242         return 0;
243     } else {
244         return 1;
245     }
246 }
247 
248 /*
249  * Adjust the point whether is in the pool(-50=<x=<50 and -50=<y=<50)
250  */
251 int isInner(pGraph graph, vertex v) {
252     int x = graph->collection[v].x;
253     int y = graph->collection[v].x;
254     if (x >= -50 && x <= 50 && y >= -50 && y <= 50) {
255         return 1;
256     } else {
257         return 0;
258     }
259 }
260 
261 /*
262  Breadth first search and find whether having a safe path to reach river bank
263  @param graph The graph stored by the adjacent table
264  @param startPoint The point we start search
265  @param dist A integer to store the edges from source to destination
266  @param path A integer to store the index of last vertex which is shortest to pass current point
267  @param safePoint A integer array to store the safe points
268  */
269 int unWeight(pGraph graph, vertex startPoint, int *dist, int *past,
270         int *safePoint) {
271     dist[startPoint] = 1;
272     /*
273      * The point index in the graph's points' collection
274      */
275     vertex w, v;
276     int counter = 0;
277     pQueue queue = createEmptyQueue();
278     addQueue(queue, startPoint);
279     if (isSafe(graph, startPoint)) {
280         safePoint[counter] = startPoint;
281         counter++;
282     }
283     while (!isQueueEmpty(queue)) {
284         w = deleteEleFromQueue(queue);
285         for (v = 0; v < graph->vertex_num; v++) {
286             if (dist[v] == -1 && isJump(graph, v, w) && isInner(graph, v)) {
287 
288                 if (isSafe(graph, v)) {
289                     safePoint[counter] = v;
290                     counter++;
291                 }
292 
293                 dist[v] = dist[w] + 1;
294                 past[v] = w;
295                 addQueue(queue, v);
296             }
297         }
298     }
299     return counter;
300 }
301 
302 /*
303  *James first jump action,similar of the isJump method,but sometimes ewe
304  *need to consider the radius if the start points, so we separate the
305  *first jump from followed jumps
306  *@param graph The graph to store points collection and some information
307  *@param startPoint_x The x-coordinate of the start point
308  *@param startPoint_y The x-coordinate of the start point
309  *@param v The index of the point in the graph's collection
310  */
311 int firstJump(pGraph graph, int startPoint_x, int startPoint_y, vertex v) {
312     if (calculateTwoPointDistance(startPoint_x, startPoint_y,
313             graph->collection[v].x, graph->collection[v].y)
314             > graph->maxDistance) {
315         return 0;
316     } else {
317         return 1;
318     }
319 }
320 
321 /*
322  * Find a minimal distance safe point from the a series safe points
323  * @param graph A graph to store point
324  * @param digt A integer array to store edges from source point to destination point
325  * @param safePoints A integer array to store the index of the safe point in graph
326  * @param length The length of the safe point array
327  */
328 int findShortestSafePoint(pGraph graph, int *digt, int *safePoints, int length) {
329     int i, safeIndex, p;
330     double minDistance = 65536, distance;
331     int shortestPoint;
332     for (i = 0; i < length; i++) {
333         safeIndex = safePoints[i];
334         p = digt[safeIndex];
335         distance = getLastDistance(graph, safeIndex) + graph->maxDistance * p;
336         if (distance < minDistance) {
337             minDistance = distance;
338             shortestPoint = safeIndex;
339         }
340     }
341     return shortestPoint;
342 }
343 
344 /*============================define a stack and some relative operators=============*/
345 typedef int stackElement;
346 typedef struct nodeStack {
347     stackElement element;
348     struct nodeStack *next;
349 } sta, *pStack;
350 
351 pStack createEmptyStack() {
352     pStack stack;
353     stack = (pStack) malloc(sizeof(sta));
354     if (stack) {
355         stack->next = NULL;
356     }
357     return stack;
358 }
359 
360 int isEmpty(pStack stack) {
361     if (stack->next == NULL) {
362         return 1;
363     } else {
364         return 0;
365     }
366 }
367 
368 void push(pStack stack, stackElement element) {
369     pStack node = (pStack) malloc(sizeof(sta));
370     node->element = element;
371     node->next = stack->next;
372     stack->next = node;
373 }
374 
375 stackElement pop(pStack stack) {
376     stackElement element;
377     pStack topHead;
378     if (isEmpty(stack)) {
379         printf("the stack is empty,can not pop");
380         return -65536;
381     } else {
382         topHead = stack->next;
383         stack->next = topHead->next;
384         element = topHead->element;
385         free(topHead);
386         return element;
387     }
388 }
389 
390 /*
391  * Search a path to destination with a path recorded array
392  * @param graph The graph to store the point
393  * @param path A integer array to store the index of last vertex which is shortest to pass current point
394  * @param length The length of the path
395  * @param destination The index of the destination in graph
396  *
397  */
398 void findPath(pGraph graph, int *path, int length, int destination) {
399     pStack stack = createEmptyStack();
400     vertex v;
401     int times = 0;
402     int index = destination;
403     push(stack, index);
404     while (v != -1) {
405         v = path[index];
406         push(stack, v);
407         times++;
408         index = v;
409     }
410 
411     pop(stack);
412     printf("%d
", times + 1);
413     while (!isEmpty(stack)) {
414         stackElement element = pop(stack);
415         printf("%d %d
", graph->collection[element].x,
416                 graph->collection[element].y);
417     }
418 }
419 
420 /*
421  * Fill a array with value
422  * @param arr The array need to be filled
423  * @param length The length of the array
424  * @param filledValue The value the array will be filled
425  */
426 void fullArray(int *arr, int length, int filledValue) {
427     int i;
428     for (i = 0; i < length; i++) {
429         arr[i] = filledValue;
430     }
431 }
432 
433 /*
434  * Is a safe path reaching bank and find the shortest path.Use no-weight
435  * searching shortest method. We let first jump separate because we consider the
436  * source is have radius is really,in order to update program in the future.
437  * So we find source adjacent points and let them to search safe path.
438  * We calculate the shortest safe point from each adjacent points searching result and store
439  * them is <code>shortPoints</code>,when all adjacent points search finishing,we calculate the
440  * shortest point from <code>shortPoints</code>.And print the path using stack.
441  *
442  *@param graph The graph to store points collection and some information
443  *@param startPoint_x The x-coordinate of the start point
444  *@param startPoint_y The x-coordinate of the start point
445  *@param v The index of the point in the graph's collection
446  *@param dist A integer to store the edges from source to destination
447  *@param path A integer to store the index of last vertex which is shortest to pass current point
448  */
449 void saveJamesBFS(pGraph graph, int startPoint_x, int startPoint_y, int *dist,
450         int *path) {
451     vertex v;
452     int safePoint[graph->vertex_num];
453     int shortestIndex = 0;
454     /*
455      *store the shortest safe point from adjacent point result
456      */
457     int shortPoints[graph->vertex_num];
458     int counter = 0;
459     int length = 0;
460     int destination;
461     for (v = 0; v < graph->vertex_num; v++) {
462         if (dist[v] == -1 && firstJump(graph, startPoint_x, startPoint_y, v)) {
463             fullArray(safePoint, graph->vertex_num, -1);
464             length = unWeight(graph, v, dist, path, safePoint);
465             if (length != 0) {
466                 shortestIndex = findShortestSafePoint(graph, dist, safePoint,
467                         length);
468                 shortPoints[counter] = shortestIndex;
469                 counter++;
470             }
471         }
472     }
473     if (counter == 0) {
474         printf("0");
475     } else {
476         /*
477          *calculate the shortest safe point from the some shorter safe point
478          */
479         destination = findShortestSafePoint(graph, dist, shortPoints, counter);
480         findPath(graph, path, graph->vertex_num, destination);
481     }
482 }
483 
484 /*
485  * Run method
486  */
487 int main() {
488     pGraph graph = buildGraph();
489     if (graph->maxDistance >= 25) {
490         printf("1");
491         return 0;
492     } else {
493         int dist[graph->vertex_num];
494         int path[graph->vertex_num];
495         fullArray(dist, graph->vertex_num, -1);
496         fullArray(path, graph->vertex_num, -1);
497         saveJamesBFS(graph, 0, 0, dist, path);
498         return 0;
499     }
500 
501 }

SaveJamesHardVersion

部分测试数据：

Sample Input 1:

17 15
10 -21
10 21
-40 10
30 -50
20 40
35 10
0 -10
-25 22
40 -40
-30 30
-10 22
0 11
25 21
25 10
10 10
10 35
-30 10

Sample Output 1:

4
0 11
10 21
10 35

Sample Input 2:

4 13
-12 12
12 12
-12 -12
12 -12

Sample Output 2:

0

但是代码在PTA只通过了67%，如果你知道为什么，可以在下面评论通知我