记:
一开始没接触过关于最短距离的算法，便开始翻阅关于图的知识，
得知关于最短距离的算法有Dijkstra算法(堆优化暂未看懂)，Bellman-Ford算法，Floyd算法，SPFA算法。
由于数据输入中存在负边，故可使用的有Dijkstra算法堆优化以及SPFA队列优化，
于是在网上找模版，却报出了运行错误。
也没看出问题，故翻阅他人笔记
其中一篇关于SPFA详解的blog:
http://blog.****.net/muxidreamtohit/article/details/7894298
让我恍然大悟，
然后就开始动笔...
第一次,10分 原因:没加结点的检查，造成死循环;
第二次,50分 原因:结点访问标记放在了判断最短距离的外面，造成了重复入队;
第三次,100分
源码如下:
1 #include <stdio.h>
2 #include <stdlib.h>
3 #define MAX 99999999
4
5 typedef struct node node_t;
6 typedef struct node
7 {
8 int n ; /*指向的结点*/
9 int v ; /*边权值*/
10 node_t *next;
11 }node;
12 typedef node *node_p;
13 node_p *e = NULL;
14
15
16 int *d; /*到各点的距离*/
17 int *vis; /*用于纪录各结点的访问记录*/
18 int *line; /*队列*/
19 int rear = 0 , front = 0; /*队列的首尾标志*/
20 int n = 0 , m = 0 ; /*n个结点,m条边*/
21
22 void init() /*初始化,以及各结点间距离的登记*/
23 {
24 node *p;
25 int i = 0 , j = 0 ;
26 int x = 0 , y = 0 , v = 0 ;
27 scanf("%d %d",&n,&m);
28
29 d = (int *)malloc(sizeof(int)*(n+1));
30 vis = (int *)malloc(sizeof(int)*(n+1));
31 line = (int *)malloc(sizeof(int)*(n+1));
32 for (i = 1 ; i <= n ; i ++)
33 {
34 d[i] = MAX;
35 vis[i] = 0;
36 line[i] = 0;
37 }
38
39 e = (node_p *)malloc(sizeof(node_p)*(n+1));
40 for (i = 1 ; i <= n ; i ++)
41 {
42 e[i] = NULL;
43 }
44
45 /*处理成邻接表*/
46 for (i = 1 ; i <= m ; i ++)
47 {
48 scanf("%d %d %d",&x,&y,&v);
49 p = (node *)malloc(sizeof(node));
50 p->n = y ;
51 p->v = v ;
52 p->next = e[x];
53 e[x] = p;
54 }
55
56 return ;
57 }
58
59 void push(int x) /*进队列*/
60 {
61 front ++;
62 if (!line[front])
63 {
64 line[front] = x ;
65 }
66 if (front == n)
67 {
68 front = front%n;
69 }
70 return ;
71 }
72
73 int pop() /*出队列*/
74 {
75 int x = 0;
76 rear ++;
77 if (line[rear])
78 {
79 x = line[rear];
80 line[rear] = 0;
81 }
82 if (rear == n)
83 {
84 rear = rear%n;
85 }
86 return x;
87 }
88
89 void SPFA(int x)
90 {
91 node *p;
92 int i = 0 , k = 0;
93
94 d[x] = 0;
95 vis[x] = 1; /*访问x并标记*/
96 push(x); /*进队*/
97 i = n;
98 while (i)
99 {
100 k = pop(); /*出队*/
101 vis[k] = 0;
102 p = e[k];
103 i --;
104 while(p != NULL)
105 {
106 if (d[k]+p->v < d[p->n])
107 {
108 d[p->n] = d[k]+p->v;
109
110 if (!vis[p->n])/*未被标记的下一个结点将进队*/
111 {
112 vis[p->n] = 1;
113 push(p->n);
114 }
115 }
116 p = p->next;
117 }
118 }
119
120 /*打印到各点的距离*/
121 for (i = 2 ; i <= n ; i ++)
122 {
123 printf("%d\n",d[i]);
124 }
125
126 return ;
127 }
128
129 int main(void)
130 {
131 init();
132 SPFA(1);
133 return 0;
134 }