Intervals (spfa + 차분 제약)
10384 단어 SPFA
1 #include <iostream>
2 #include <cstring>
3 #include <queue>
4 #include <cstdio>
5 using namespace std;
6 const int N = 50000+10;
7 const int INF = 1<<27;
8 int n,max_n,min_n,cnt;
9 bool vis[N];
10 int dis[N];
11 int root[N];
12 struct node{
13 int v,next,dis;
14 }eg[4*N];
15 void add(int u,int v,int w)
16 {
17 eg[cnt].v=v;
18 eg[cnt].next=root[u];
19 eg[cnt].dis=w;
20 root[u]=cnt++;
21 }
22 bool relax(int u,int v,int w)
23 {
24 if(dis[v]<dis[u]+w)
25 {
26 dis[v]=dis[u]+w;
27 return 1;
28 }
29 return 0;
30 }
31 void spfa()
32 {
33 int i;
34 for(i=min_n;i<=max_n;i++)
35 {
36 dis[i]=-INF;vis[i]=0;
37 }
38 dis[min_n]=0;vis[min_n]=1;
39 queue<int> q;
40 q.push(min_n);
41 while(!q.empty())
42 {
43 int u=q.front();
44 q.pop();vis[u]=0;
45 for(i=root[u];i!=-1;i=eg[i].next)
46 {
47 int v=eg[i].v;
48 int d=eg[i].dis;
49 if(relax(u,v,d)&&!vis[v])
50 {
51 vis[v]=1;
52 q.push(v);
53 }
54 }
55 }
56 }
57 int main()
58 {
59 int u,v,w,i;
60 while(cin>>n)
61 {
62 max_n=-INF;min_n=INF;cnt=0;
63 memset(root,-1,sizeof(root));
64 for(i=0;i<n;i++)
65 {
66 scanf("%d%d%d",&u,&v,&w);
67 u++;v++;
68 max_n=max(max_n,v);
69 min_n=min(min_n,u-1);
70 add(u-1,v,w);
71 }
72 for(i=min_n;i<=max_n;i++)//0<=dis[i]-dis[i-1]<=1
73 {
74 add(i,i-1,-1);
75 add(i-1,i,0);
76 }
77 spfa();
78 cout<<dis[max_n]<<endl;
79 }
80 return 0;
81 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU4276 The Ghost Blows Light SPFA & 트리 dp제목의 소개와 사고방식은 아래의 블로그를 완전히 참고하였다.http://blog.csdn.net/acm_cxlove/article/details/7964739 이 문제를 푸는 것은 주로 SPFA 코드에 대한 자신의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.