两道差分约束
http://acm.hdu.edu.cn/showproblem.php?pid=1384
#include <iostream> #include <cstring> #include <cstdio> #include <queue> using namespace std ; const int INF=0xfffffff ; int vis[50005],dis[50005] ; int m ; int cnt ; int head[50005] ; struct node{ int s,t,v,nxt ; }e[200005] ; void add(int s,int t,int v) { e[cnt].s=s ; e[cnt].t=t ; e[cnt].v=v ; e[cnt].nxt=head[s] ; head[s]=cnt++ ; } int minn,maxn ; int spfa(int s,int t) { for(int i=minn ;i<=maxn ;i++) dis[i]=-INF ; dis[s]=0 ; queue <int> q ; q.push(s) ; while(!q.empty()) { int u=q.front() ; q.pop() ; vis[u]=0 ; for(int i=head[u] ;i!=-1 ;i=e[i].nxt) { int tt=e[i].t ; if(dis[tt]<e[i].v+dis[u]) { dis[tt]=e[i].v+dis[u] ; if(!vis[tt]) { vis[tt]=1 ; q.push(tt) ; } } } } return dis[t] ; } int main() { while(~scanf("%d",&m)) { cnt=0 ; memset(head,-1,sizeof(head)) ; int s,t,v ; minn=INF ; maxn=-1 ; for(int i=0 ;i<m ;i++) { scanf("%d%d%d",&s,&t,&v) ; minn=min(minn,s) ; maxn=max(maxn,t+1) ; add(s,t+1,v) ; } for(int i=minn ;i<=maxn ;i++) { add(i+1,i,-1) ; add(i,i+1,0) ; } memset(vis,0,sizeof(vis)) ; printf("%d ",spfa(minn,maxn)) ; } return 0 ; }
http://acm.hdu.edu.cn/showproblem.php?pid=3592
#include <iostream> #include <queue> using namespace std ; const int INF=0xfffffff ; int n ; struct node{ int s,t,v,nxt ; }e[200005] ; int cnt ; int head[50005],vis[50005],dis[50005],ct[50005] ; void add(int s,int t,int v) { e[cnt].s=s ; e[cnt].t=t ; e[cnt].v=v ; e[cnt].nxt=head[s] ; head[s]=cnt++ ; } int spfa() { for(int i=2 ;i<=n ;i++) dis[i]=INF ; dis[1]=0 ; queue <int> q ; q.push(1) ; ct[1]++ ; while(!q.empty()) { int u=q.front() ; q.pop() ; vis[u]=0 ; for(int i=head[u] ;i!=-1 ;i=e[i].nxt) { int tt=e[i].t ; if(dis[tt]>dis[u]+e[i].v) { dis[tt]=dis[u]+e[i].v ; if(!vis[tt]) { ct[tt]++ ; if(ct[tt]>=n)return 0 ; vis[tt]=1 ; q.push(tt) ; } } } } return 1 ; } int main() { int t ; scanf("%d",&t) ; while(t--) { memset(head,-1,sizeof(head)) ; cnt=0 ; int x,y ; scanf("%d%d%d",&n,&x,&y) ; int s,t,v ; for(int i=0 ;i<x ;i++) { scanf("%d%d%d",&s,&t,&v) ; add(s,t,v) ; } for(int i=0 ;i<y ;i++) { scanf("%d%d%d",&s,&t,&v) ; add(t,s,-v) ; } for(int i=1 ;i<n ;i++) add(i+1,i,0) ; memset(vis,0,sizeof(vis)) ; memset(ct,0,sizeof(ct)) ; if(!spfa())puts("-1") ; else if(dis[n]==INF)puts("-2") ; else printf("%d ",dis[n]) ; } return 0 ; }