题意：
有n个同学分糖，给m组数据i,j,k，要求第j个同学分到的糖不能比第i个同学分到的糖多于k个。要求第1个同学与第n个同学之间糖的个数差距最大，求最大的差距。
要点：
这题思路不难，既然要求1~n的差距最大，那每组数据刚好取k，整个就是一个最短路问题，dis数组存储的就是最多拿到的糖。但这题时间卡的实在是太紧，SPFA用STL都会超时，而且数据太大，必须要用邻接表存储边。所以看了一下网上大神的代码，用一个栈来维护原本的队列，然后用链表来存储同一个起点的所有边，这样可以到450ms，这题也说明了SPFA算法的时间不稳定。还可以用dijstra+heap做。
| 15391447 | Seasonal | 3159 | Accepted | 1960K | 454MS | C++ | 1078B | 2016-04-14 16:43:44 |
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define INF 0x3f3f3f3f
struct edge
{
int v, len;
int next;
}e[150005];
int dis[30005],adj[30005];
bool vis[30005];
int n, m,tot;//tot为总边数
void add_edge(int u, int v, int len)//增加同一个起点的边数,链表存储
{
e[tot].v = v;
e[tot].len = len;
e[tot].next = adj[u];//如果只有一条边就是-1
adj[u] = tot++; //adj用来指向下一个终点对应的下标
}
void spfa()
{
memset(dis, INF, sizeof(dis));
memset(vis, true, sizeof(vis));
int stack[30005];
int top = 0;
stack[++top] = 1;
vis[1] = false;
dis[1] = 0;
while (top)
{
int u = stack[top--]; //stack堆栈用来存储起点
vis[u] = true;
for (int i = adj[u]; i != -1; i = e[i].next)//遍历同一个起点的所有终点
{
int v = e[i].v;
int len = e[i].len;
if (dis[v] > dis[u] + len)
{
dis[v] = dis[u] + len;
if (vis[v])
{
stack[++top] = v;
vis[v] = false;
}
}
}
}
}
int main()
{
int u, v, len;
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++)
adj[i] = -1;
tot = 0;
while(m--)
{
scanf("%d%d%d", &u,&v,&len);
add_edge(u, v, len);
}
spfa();
printf("%d\n", dis[n]);
return 0;
}