// 思路 ：
// 图建好后 剩下的就和上一篇的 火烧连营那题一样了 求得解都是一样的
// 所以稍微改了就过了
// 最下面还有更快的算法 速度是这个算法的2倍
#include <iostream>
#include <map>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MOD 1000000007
#define maxn 150010
#define maxm 50010
struct node{
int to;
int next;
int val;
}E[maxn];
int num;
int V[maxm];
int d[maxm],cnt[maxm];
bool f[maxm];
bool sfpa(int s,int t){// s既表示起点 有表示节点个数
queue <int> Q;
int u,v;
int e;
Q.push(s);
d[s]=;
f[s]=true;
while(!Q.empty()){
u=Q.front(); Q.pop();
cnt[u]++;
if(cnt[u]>s) return false;
f[u]=false;
for(e=V[u];e!=-;e=E[e].next){
v=E[e].to;
if(d[u]+E[e].val<d[v]){
d[v]=d[u]+E[e].val;
if(!f[v])
{
f[v]=true;
Q.push(v);
}
}
}
}
return true;
}
int main(){
int i,j,k;
int n,m;
while(scanf("%d",&n)!=EOF){
for(i=;i<=;i++)
{
V[i]=-;
d[i]=MOD;
cnt[i]=;
f[i]=false;
}
num=;
m=;
while(n--){
scanf("%d %d %d",&i,&j,&k);
m=max(m,max(i,j));
E[num].to=i-;
E[num].val=-k;
E[num].next=V[j];
V[j]=num++;
}
for(i=m;i>=;i--){
E[num].to=i;
E[num].val=;
E[num].next=V[i-];
V[i-]=num++; E[num].to=i-;
E[num].val=;
E[num].next=V[i];
V[i]=num++;
}
// if(
sfpa(m,);
printf("%d\n",-d[]);
// else
// printf("Bad Estimations\n"); } } // 下面给出更快的算法
// 主要思路：
更好的方法是：
1) 先仅仅用约束条件①构造网络图，各顶点到源点的最短距离初始为0，这是因为Si – Smx
<= 0，所以源点到各顶点的最短距离肯定是小于0的。注意本题中源点是S[mx]。
第4章 最短路径问题
- 201 -
2) 即刻用Bellman-Ford算法求各顶点到源点的最短路径（注意Bellman-Ford算法的思想），
在每次循环中，约束条件①判断完后再加上约束条件②和③的判断。
a) 约束条件②的判断：
S[i] <= S[i-1] + 1 等效于 S[i] – S[mx] <= S[i-1] – S[mx] + 1。
假设dist[i]为源点mx到顶点Si的最短路径，那么S[i] – S[mx]就是dist[i]，S[i-1] – S[mx] + 1
就是dist[i-1] + 1，即如果顶点Si到源点的最短路径长度大于Si-1到源点的最短路径长度加1，则
修改dist[i]为dist[i-1] + 1。
b) 约束条件③的判断：
S[i-1]<=S[i] 等效于 S[i-1] – S[mx] <= S[i] – S[mx]。 详情见代码 #include <cstdio>
#include <cstring>
#define inf 99999
#define EMAX 50002
structe
{
int u, v, w; //边：起点、终点、权值
}edges[EMAX];
int n; //区间的个数
int dist[EMAX]; //求得的从源点到各顶点的最短路径
int mn; //所有区间左端点的最小值
int mx; //所有区间右端点的最大值
void init( ) //初始化函数
{
int i;
for( i=0; i<EMAX; i++ ) //将源点到各顶点的最短路径长度初始为0
dist[i] = 0;
//这是因为Si-Smx<=0，所以源点到各顶点的最短距离肯定是小于0的
//Si:Z中小于等于i 的元素个数，即S[i] = |{s|s∈Z,s<=i}|
mx = 1; mn = inf;
}
bool bellman_ford( )
{
int i, t; //循环变量和临时变量
int f = 1;//标志变量，为提前结束Bellman-Ford算法的标志变量
//只要某次循环过程中,没能改变源点到各顶点的最短距离，则可以提前结束
while( f )
{
f = 0;
//Bellman-Ford算法本身的循环，考虑每条边是否能改变源点到各顶点的最短距离
for( i=0; i<n; i++ )
{
t = dist[edges[i].u] + edges[i].w;
if( dist[edges[i].v]>t )
{
dist[edges[i].v] = t; f = 1;
}
}
//根据约束条件s[i] <= s[i-1] + 1进一步修改s[i]值
for( i=mn; i<=mx; i++ )
{
t = dist[i-1] + 1;
if( dist[i]>t )
{
dist[i] = t; f = 1;
}
}
//根据约束条件s[i-1] <= s[i], 进一步修改s[i-1]值
for( i=mx; i>=mn; i-- )
{
t = dist[i];
if( dist[i-1]>t )
{
dist[i-1] = t; f = 1;
}
}
}
return true;
}
int main( )
{
while( scanf("%d", &n) != EOF )
{
init( );
int i;
int u, v, w; //区间的两个端点、ci
for( i=0; i<n; i++ )
{
scanf( "%d %d %d", &u, &v, &w );
//构造边<v,u-1,-w>
edges[i].u = v, edges[i].v = u - 1, edges[i].w = -w;
if( mn>u ) mn = u;//求得mn为所有区间左端点的最小值
if( mx<v ) mx = v;//求得mx为所有区间右端点的最大值
}
bellman_ford( ); printf( "%d\n", dist[mx] - dist[mn-1] );
}
return 0;
}