hdu 5168 Legal path

hdu 5168 Legal path

 

 

題意：
一個有向圖，給定起點終點，每條邊上有權值。
一條合法的路徑定義為相鄰邊的權值之差不小於K的路徑，即路徑上每條邊的權值至少要比上一條邊的權值大K，如果上一條邊存在。合法路徑的長度定義為路徑上的邊權值總和。
求從起點到終點的合法路徑的最短長度。
限制：
有多組數據，第一行為數據組數T（T≤10）。
對於每組數據，第一行為三個整數n,m,K，n,m分別表示這組數據的有向圖的點數，邊數，起點為1號點，終點為n號點。
在接下來有m行，每行有三個整數x,y,z，表示從x到y有一條權值為z的邊。
2 <= n <= 100,000
0 <= m <= 200,000
1 <= K,z <= 1,000,000,000
1 <= x,y <= n
思路：
先把所有邊按權值從小到大排序，因為權值大的邊是不可能連到權值小的邊上。
然後按邊更新dp數組


dp[i]是一個vector，裡面保存著：(原點到點i的最後一條邊的權值c , 原點到點i的距離s)
ps：這個信息應該要存在一個關系，如vector裡面的信息為：
(c1,s1),(c2,s2),...,(ci,si),...,(cj,sj)
對於任意isj，這是個關鍵點。


每到一條邊我們都可以知道這條邊的出發點fr，到達點to，和邊權c。
然後按照邊權c-k在dp[fr]中二分查找合適的信息，然後用來更新dp[to]。

跑完m條邊就能得到答案，復雜度為O(mlog(m))。

 

附上一組測試數據：

1

5 6 3
1 2 3
2 3 6
3 4 10
4 5 13
2 3 1
2 4 11

 

 

C++ Code 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106   /*hdu 5168 Legal path
題意：
一個有向圖，給定起點終點，每條邊上有權值。
一條合法的路徑定義為相鄰邊的權值之差不小於K的路徑，即路徑上每條邊的權值至少要比上一條邊的權值大K，如果上一條邊存在。合法路徑的長度定義為路徑上的邊權值總和。
求從起點到終點的合法路徑的最短長度。
限制：
有多組數據，第一行為數據組數T（T≤10）。
對於每組數據，第一行為三個整數n,m,K，n,m分別表示這組數據的有向圖的點數，邊數，起點為1號點，終點為n號點。
在接下來有m行，每行有三個整數x,y,z，表示從x到y有一條權值為z的邊。
2 <= n <= 100,000
0 <= m <= 200,000
1 <= K,z <= 1,000,000,000
1 <= x,y <= n
思路：
先把所有邊按權值從小到大排序，因為權值大的邊是不可能連到權值小的邊上。
然後按邊更新dp數組

dp[i]是一個vector，裡面保存著：(原點到點i的最後一條邊的權值c , 原點到點i的距離s)
ps：這個信息應該要存在一個關系，如vector裡面的信息為：
(c1,s1),(c2,s2),...,(ci,si),...,(cj,sj)
對於任意isj，這是個關鍵點。

每到一條邊我們都可以知道這條邊的出發點fr，到達點to，和邊權c。
然後按照邊權c-k在dp[fr]中二分查找合適的信息，然後用來更新dp[to]。
跑完m條邊就能得到答案，復雜度為O(mlog(m))。
*/
#include
#include
#include
#include
#include
using namespace std;
#define LL __int64
#define MP make_pair
#define PB push_back
const int N=100005;
const LL INF=(LL)0x3f3f3f3f*0x3f3f3f3f;
struct Edge{
int fr,to;
LL c;
Edge(){};
Edge(int _fr,int _to,LL _c){
fr=_fr;
to=_to;
c=_c;
}
}E[2*N];
bool cmp1(Edge a,Edge b){
return a.c }
struct Dt{
LL c,s;
Dt(){}
Dt(LL _c,LL _s){
c=_c;
s=_s;
}
};
bool cmp2(Dt a,Dt b){
if(a.c==b.c) return a.s>b.s;
return a.c }
vector

dp[N];
int n,m,k;
void init(){
for(int i=1;i<=n;++i)
dp[i].clear();
}
int main(){
int T;
scanf(%d,&T);
while(T--){
scanf(%d%d%d,&n,&m,&k);
init();
for(int i=0;i scanf(%d%d%I64d,&E[i].fr,&E[i].to,&E[i].c);
}
sort(E,E+m,cmp1);
for(int i=0;i int fr=E[i].fr,to=E[i].to;
LL c=E[i].c;
if(fr==1){
if(dp[to].size()==0)
dp[to].PB(Dt(E[i].c,E[i].c));
else if(dp[to][dp[to].size()-1].s>E[i].c)
dp[to].PB(Dt(E[i].c,E[i].c));
}
else{
if(dp[fr].size()==0) continue;
int p=upper_bound(dp[fr].begin(),dp[fr].end(),Dt(E[i].c-k,-INF),cmp2)-dp[fr].begin();
if(p==0) continue;
else if(p>0 && p else if(dp[fr][dp[fr].size()-1].c<=E[i].c-k) p=dp[fr].size()-1;
else continue;
if(dp[to].size()==0)
dp[to].PB(Dt(E[i].c,dp[fr][p].s+E[i].c));
else if(dp[to][dp[to].size()-1].s>dp[fr][p].s+E[i].c)
dp[to].PB(Dt(E[i].c,dp[fr][p].s+E[i].c));
}
}
if(dp[n].size()==0) puts(-1);
else printf(%I64d ,dp[n][dp[n].size()-1].s);
}
return 0;
}