lg1250

发表于 | 阅读数 次

链接:lg1250

题解

  • 求最小值，即求最长路，区间上的约束问题，结合题意很显然可以转换成前缀和的点上的约束问题，注意要列出所有约束条件。
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<queue>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=1e6+7;
    int to[N],nxt[N],w[N],head[N],inq[N],dis[N],cnt,n,m;
    inline void adde(int a,int b,int c){
    	to[++cnt]=b;
    	w[cnt]=c;
    	nxt[cnt]=head[a];
    	head[a]=cnt;
    }
    void spfa(){
    	queue<int>q;
    	q.push(0);
    	dis[0]=0;inq[0]=1;
    	while(!q.empty()){
    		int k=q.front();
    		q.pop();
    		inq[k]--;
    		for(int i=head[k];i;i=nxt[i])if(dis[to[i]]<dis[k]+w[i]){
    			dis[to[i]]=dis[k]+w[i];
    			if(inq[to[i]]==0){
    				inq[to[i]]++;
    				q.push(to[i]);
    			}
    		}
    	}
    }
    int main(){
    	scanf("%d%d",&n,&m);
    	memset(dis,-1,sizeof dis);
    	rep(i,0,n-1)adde(i+1,i,-1);
    	rep(i,0,n-1)adde(i,i+1,0);
    	rep(i,1,m){
    		int a,b,c;
    		scanf("%d%d%d",&a,&b,&c);
    		adde(a-1,b,c);
    	}
    	spfa();
    	printf("%d\n",dis[n]);
    	return 0;
    }