记:
一开始没接触过关于最短距离的算法，便开始翻阅关于图的知识，
得知关于最短距离的算法有Dijkstra算法(堆优化暂未看懂)，Bellman-Ford算法，Floyd算法，SPFA算法。
由于数据输入中存在负边，故可使用的有Dijkstra算法堆优化以及SPFA队列优化，
于是在网上找模版，却报出了运行错误。
也没看出问题，故翻阅他人笔记
其中一篇关于SPFA详解的blog:
http://blog.csdn.net/muxidreamtohit/article/details/7894298
让我恍然大悟，
然后就开始动笔...
第一次,10分 原因:没加结点的检查，造成死循环;
第二次,50分 原因:结点访问标记放在了判断最短距离的外面，造成了重复入队;
第三次,100分
源码如下:
#include <stdio.h>
#include <stdlib.h>
#define MAX 99999999 typedef struct node node_t;
typedef struct node
{
int n ; /*指向的结点*/
int v ; /*边权值*/
node_t *next;
}node;
typedef node *node_p;
node_p *e = NULL; int *d; /*到各点的距离*/
int *vis; /*用于纪录各结点的访问记录*/
int *line; /*队列*/
int rear = , front = ; /*队列的首尾标志*/
int n = , m = ; /*n个结点,m条边*/ void init() /*初始化,以及各结点间距离的登记*/
{
node *p;
int i = , j = ;
int x = , y = , v = ;
scanf("%d %d",&n,&m); d = (int *)malloc(sizeof(int)*(n+));
vis = (int *)malloc(sizeof(int)*(n+));
line = (int *)malloc(sizeof(int)*(n+));
for (i = ; i <= n ; i ++)
{
d[i] = MAX;
vis[i] = ;
line[i] = ;
} e = (node_p *)malloc(sizeof(node_p)*(n+));
for (i = ; i <= n ; i ++)
{
e[i] = NULL;
} /*处理成邻接表*/
for (i = ; i <= m ; i ++)
{
scanf("%d %d %d",&x,&y,&v);
p = (node *)malloc(sizeof(node));
p->n = y ;
p->v = v ;
p->next = e[x];
e[x] = p;
} return ;
} void push(int x) /*进队列*/
{
front ++;
if (!line[front])
{
line[front] = x ;
}
if (front == n)
{
front = front%n;
}
return ;
} int pop() /*出队列*/
{
int x = ;
rear ++;
if (line[rear])
{
x = line[rear];
line[rear] = ;
}
if (rear == n)
{
rear = rear%n;
}
return x;
} void SPFA(int x)
{
node *p;
int i = , k = ; d[x] = ;
vis[x] = ; /*访问x并标记*/
push(x); /*进队*/
i = n;
while (i)
{
k = pop(); /*出队*/
vis[k] = ;
p = e[k];
i --;
while(p != NULL)
{
if (d[k]+p->v < d[p->n])
{
d[p->n] = d[k]+p->v; if (!vis[p->n])/*未被标记的下一个结点将进队*/
{
vis[p->n] = ;
push(p->n);
}
}
p = p->next;
}
} /*打印到各点的距离*/
for (i = ; i <= n ; i ++)
{
printf("%d\n",d[i]);
} return ;
} int main(void)
{
init();
SPFA();
return ;
}