1 条题解
-
0
C++ :
#include<bits/stdc++.h> using namespace std; const int N=50010,M=3*N+10; int h[N],e[M],ne[M],w[M],idx; bool st[N]; int dist[N]; int n,m; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void spfa() { queue<int> q; memset(dist,-0x3f,sizeof dist); q.push(0); dist[0]=0; st[0]=true; while(q.size()) { int t=q.front(); st[t]=false; q.pop(); for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(dist[j]<dist[t]+w[i]) { dist[j]=dist[t]+w[i]; if(!st[j]) { q.push(j); st[j]=true; } } } } } int main() { cin>>n; memset(h,-1,sizeof h); for(int i=1;i<=50001;i++) { add(i-1,i,0); add(i,i-1,-1); } while(n--) { int a,b,c; cin>>a>>b>>c; a++,b++; add(a-1,b,c); } spfa(); cout<<dist[50001]; return 0; }
- 1
信息
- ID
- 758
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者