Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3332 Accepted Submission(s):
1227
#include<stdio.h>
#include<string.h>
#include<queue>
#define INF 0x3f3f3f
#define MAX 200000
#include<algorithm>
using namespace std;
int n,ans;
int maxl,maxr;
int vis[MAX],dis[MAX];
int head[MAX];
struct node
{
int u,v,w;
int next;
}edge[MAX];
void add(int u,int v,int w)
{
edge[ans].u=u;
edge[ans].v=v;
edge[ans].w=w;
edge[ans].next=head[u];
head[u]=ans++;
}
void init()
{
ans=0;
maxl=INF;
maxr=0;
memset(head,-1,sizeof(head));
}
void getmap()
{
int i,j,a,b,c;
while(n--)
{
scanf("%d%d%d",&a,&b,&c);
maxl=min(maxl,a);
maxr=max(maxr,b);
add(b,a-1,-c);
}
for(i=maxl;i<=maxr;i++)
{
add(i,i-1,0);
add(i-1,i,1);
}
}
void spfa()
{
int i,j;
queue<int>q;
memset(vis,0,sizeof(vis));
for(i=maxl-1;i<=maxr;i++)//以maxr为源点,也可以以maxl为源点,不过要对建图稍作修改
dis[i]=INF;
dis[maxr]=0;
vis[maxr]=1;
q.push(maxr);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(i=head[u];i!=-1;i=edge[i].next)
{
int top=edge[i].v;
if(dis[top]>dis[u]+edge[i].w)
{
dis[top]=dis[u]+edge[i].w;
if(!vis[top])
{
vis[top]=1;
q.push(top);
}
}
}
}
printf("%d\n",-dis[maxl-1]);
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
init();
getmap();
spfa();
}
return 0;
}
原文:http://www.cnblogs.com/tonghao/p/4743583.html