这题目，我差点彻底崩溃了，郁闷死了，一开始一直TLE，原来只有一个测试数据，这叫我情何以堪……
后来，还发现了一个错误，就是构图时候，最大节点跟最小节点还是要标记一下比较好，我本来是默认0是最小节点的，可是在后面添加新边的时候又添加了一个0节点，唉
就是Sbi+1-Sai>=Ci，这样来添加边计较保险
用数组模拟队列来实现SPFA的时候，数组要绝对的足够大，我就这样RE了无数次，最后Q[maxn*10]才过的，但此时内存已经很大了
不过也可以直接用STL里面的queue来做，方便很多，内存也不算很大
还有用栈实现的，这个就很省内存啦
为什么用栈写有时候会很快呢？ 首先它很节省空间，因为最多有v-1个节点同时在栈内。其次，它在栈底的点并不容易出栈，所以等到这些节点出栈的时候，它已经被松弛的差不多了。说白了还是一个概率型优化方法。
spfa是一个不稳定的算法，用队列实现有点像广搜。当然大家可以用深搜实现一下。因为即使用栈写，那也是广度优先搜索的思路。因为它是‘一层一层’执行，而深搜是‘一个一个’执行。所以用深搜的思路写，效率可想而知了。
下面是俩种方式的SPFA：
数组模拟队列实现
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXN 50005
#define INF 0x6fffffff
struct Edge{
int v;
int w;
int next;
}edge[150000];
int head[MAXN];
bool vis[MAXN];
int dis[MAXN];
int stack[MAXN*10];
int n;
int ind;
int Max,Min;
void add_edge(int u,int v,int w)
{
edge[ind].v=v;
edge[ind].w=w;
edge[ind].next=head[u];
head[u]=ind++;
}
void Init(int e)
{
for(int i=0;i<=e;i++)
{
vis[i]=false;
dis[i]=-INF;
}
}
void spfa()
{
Init(Max);
dis[Min]=0;
int begin,end;
begin = end = 0;
stack[end++] = Min;
vis[Min] = true;
while(begin<end)
{
int t = stack[begin++];
for(int j = head[t];j!=-1;j = edge[j].next)
{
if(dis[edge[j].v]<edge[j].w+dis[t])
{
dis[edge[j].v] = edge[j].w+dis[t];
if(!vis[edge[j].v])
{
vis[edge[j].v] = true;
stack[end++] = edge[j].v;
}
}
}
vis[t] = false;
}
}
int main() {
scanf("%d",&n);
memset(head,-1,sizeof(head));
int u,v,w;
ind=0;
Max=0;Min=INF;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&u,&v,&w);
if(v+1>Max)Max=v+1;
if(u<Min)Min=u;
add_edge(u,v+1,w);
}
for(int i=Min;i<Max;i++)
{
add_edge(i,i+1,0);
add_edge(i+1,i,-1);
}
spfa();
// for(int i=Min;i<=Max;i++)printf("%d\n",dis[i]);
printf("%d\n",dis[Max]);
//printf("%d %d\n",Max,Min);
return 0;
}
用数组模拟栈实现
#include<stdio.h>
#include<stdlib.h>
#define INF 0xfffffff
#define NN 50004
#define MM 150004
int edNum, maxn;
int mark[NN];
int root[NN];
int dis[NN];
int stack[NN];
struct node{
int e, v,next;
}edge[MM];
void Init(){
int i;
for (i = 0; i < NN; i++){
mark[i] = 0;
root[i] = -1;
dis[i] = INF;
}
}
void add(int a, int b, int c){
edge[edNum].e = b;
edge[edNum].v = c;
edge[edNum].next = root[a];
root[a] = edNum++;
}
void Spfa()
{
int i, cur, nxt, tmp, top = 0;
for (i = 0; i <= maxn; i++){
if (root[i] != -1){
stack[++top] = i;
mark[i] = 1;
}
}
// 这里需要注意，要将终点置零，求的就是别的点到终点maxn的距离
dis[maxn] = 0;
while (top){
cur = stack[top--];
mark[cur] = 0;
tmp = root[cur];
while (tmp != -1){
nxt = edge[tmp].e;
if (dis[nxt] > dis[cur] + edge[tmp].v){
dis[nxt] = dis[cur] + edge[tmp].v;
if (!mark[nxt]){
mark[nxt] = 1;
stack[++top] = nxt;
}
}
tmp =edge[tmp].next;
}
}
}
int main()
{
int n, i, a, b, c;
scanf("%d", &n);
maxn = 0;
edNum = 0;
Init();
for (i = 1; i <= n; i++){
scanf("%d%d%d", &a, &b, &c);
add(b + 1, a, -c);
if (b + 1 > maxn){
maxn = b + 1;
}
}
for (i = 0; i <= maxn; i++){
add(i + 1, i, 0);
add(i, i + 1, 1);
}
Spfa();
//输出的时候也要注意，是起点到终点的距离的负值
printf("%d\n", -dis[0]);
// system("pause");
return 0;
}