Charles in Charge

 1 ///迪杰斯特拉算法，从小的点开始更新
 2 #include <bits/stdc++.h>
 3 typedef long long ll;
 4 const int maxn = 5000100;
 5 const ll INF = 1e18+9;
 6 using namespace std;
 7 
 8 ll x[maxn],y[maxn],z[maxn];
 9 vector<pair<ll,ll> >v[maxn];
10 priority_queue<pair<ll,ll> >Q;
11 ll n,m,k,ruler;
12 ll length[maxn];
13 
14 bool dij(ll len){
15 
16     ll i;
17     for(i=0;i<=n;i++){
18         v[i].clear();
19         length[i] = INF;
20     }
21 
22     for(i=1; i<=m; i++){
23         if( z[i]<=len ){
24             v[x[i]].push_back(make_pair(y[i],z[i]));
25             v[y[i]].push_back(make_pair(x[i],z[i]));
26         }
27     }
28     Q.push(make_pair(0,1));
29     length[1] = 0;
30 
31     while( !Q.empty()){
32         ll a, b, c, d;
33         a = Q.top().second;
34         b = Q.top().first;
35         Q.pop();
36         if( b>length[a] ) continue;
37         for( i=0;i<v[a].size(); i++){
38             c = v[a][i].first;
39             d = v[a][i].second;
40             if( length[c]>length[a]+d ){
41                 length[c] = length[a]+d;
42                 Q.push(make_pair(-length[c],c));///优先队列从大到小排，为了从小到大排，我们存入一个负的值
43             }
44         }
45     }
46 
47     if( length[n]*100<=ruler*(100+k)) return true;
48     else return false;
49 }
50 
51 int main()
52 {
53     ll i,mid=-1,right,left;
54     scanf("%lld%lld%lld",&n,&m,&k);
55 
56     for(i=1;i<=m;i++){
57         scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
58     }
59 
60     right = 1e9+7;
61     left = 0;
62     dij(1e9+7);
63     ruler = length[n];
64 
65     while( left<right ){
66         mid = (left+right)>>1;
67         if( dij(mid) ){
68             right = mid;
69         }
70         else left = mid+1;
71     }
72     printf("%lld\n",left);
73     return 0;
74 }