HDU 5168

把边按权值排序后，就相当于求一个子序列以1开始和以n结束。由于边权递增，而且相差>=k，所以，边的顺序也必定是递增的。知道，当处理一条出边时，必定是从入边选择一条最优的边，考虑两个因素，入边的权值和入边以前的总的代价。优化很容易想到，每个结点维护一个数组，就不需要从头扫描边数组了。但这个维护的结点的数组在两个因素符合什么条件呢。。。卡住了。。

参考了题解之后，是按入边来维护，当入边权值增大而总代价下降。这样，二分查找出总代价最小而且符合边约束的。要知道，入边权值增大是自然符合的，因为边数组在开始时就已经由小到大排列。所以，当处理到目的顶点v，到达V的总代价比结点数组的最高点还小，则把该边加入到结点数组中即可。

其中，二分使用upper_bound查找上界，学习了http://blog.csdn.net/whai362/article/details/43385107，谢谢了。。。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <vector>
 7 #define LL __int64
 8 using namespace std;
 9 const LL INF=(LL)0x3f3f3f3f*0x3f3f3f3f;
10 const int N=100010;
11 const int M=200020;
12 
13 struct TEdge{
14     int u,v,w;
15     bool operator<(const TEdge& a)const {
16         if(w<a.w) return true;
17         return false;
18     }
19 }Cedge[M];
20 int tot;
21 struct Point{
22     int lw;
23     LL alw;
24     Point(int c,LL e){lw=c; alw=e;}
25 };
26 
27 vector<Point>point[N];
28 int n,m,k;
29 
30 void addedge(int u,int v,int w){
31     Cedge[tot].u=u;
32     Cedge[tot].v=v;
33     Cedge[tot].w=w;
34     tot++;
35 }
36 
37 void Push_into(int p,Point t){
38     point[p].push_back(t);
39 }
40 
41 bool cmp(Point a,Point b){
42     if(a.lw==b.lw) return a.alw>b.alw;
43     return a.lw<b.lw;
44 }
45 
46 int main(){
47     int T,u,v,w,sz;
48     scanf("%d",&T);
49     while(T--){
50         scanf("%d%d%d",&n,&m,&k);
51         tot=0;
52         for(int i=1;i<=n;i++){
53             point[i].clear();
54         }
55         for(int i=1;i<=m;i++){
56             scanf("%d%d%d",&u,&v,&w);
57             addedge(u,v,w);
58         }
59         sort(Cedge,Cedge+tot);
60         for(int i=0;i<tot;i++){
61             u=Cedge[i].u;
62             v=Cedge[i].v;
63             if(u==1){
64                 if(point[v].empty()){
65                     Push_into(v,Point(Cedge[i].w,Cedge[i].w));
66                 }
67                 else{
68                     if(point[v][point[v].size()-1].alw>Cedge[i].w){
69                         Push_into(v,Point(Cedge[i].w,Cedge[i].w));
70                     }
71                 }
72                 continue;
73             }
74             if(point[u].empty()) continue;
75             else {
76                 int p=upper_bound(point[u].begin(),point[u].end(),Point(Cedge[i].w-k,-INF),cmp)-point[u].begin();
77                 if(p==0) continue;
78                 else if(p>0 && p<point[u].size()) --p;
79                 else if(point[u][point[u].size()-1].lw<=Cedge[i].w-k) p=point[u].size()-1;
80                 else continue;
81                 if(point[v].empty())
82                     Push_into(v,Point(Cedge[i].w,point[u][p].alw+(LL)Cedge[i].w));
83                 else if(point[v][point[v].size()-1].alw>point[u][p].alw+(LL)Cedge[i].w)
84                     Push_into(v,Point(Cedge[i].w,point[u][p].alw+(LL)Cedge[i].w));
85             }
86         }
87         if(point[n].empty())
88         printf("-1
");
89         else printf("%I64d
",point[n][point[n].size()-1].alw);
90     }
91     return 0;
92 }

View Code