2019 ACM-ICPC全国邀请赛（西安） M.Travel 二分+判联通

https://nanti.jisuanke.com/t/39280

讲道理这题写bfs求最大边权限制下从1到n的最短步数，然后二分判一下就行了。

然鹅我还是直接套了dij，一开始纠结dij能不能过，后来同学帮讲了一下发现由于二分的存在还是没问题的。

数论还没怎么学，D的dp也先不补了，窝dp奇差。不过图论还是要补的，而且这题好像全世界都会。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define INF 0x3f3f3f3f
 4 #define MAXN 100050
 5 typedef pair<int, int> P;
 6 
 7 struct edge { int to, cost;
 8     edge (int too, int costt) { to = too; cost = costt; }
 9 };
10 vector <edge> G[MAXN];
11 void addedge (int u, int v, int w) {
12     G[u].push_back (edge (v, w));
13 }
14 
15 int dis[MAXN], cnt[MAXN];
16 int n, m,c,d,e;
17 
18 bool dijkstra (int k) {
19     priority_queue<P, vector<P>, greater<P> > que;
20     fill (dis, dis + n + 1, INF);
21     fill (cnt,cnt+n+1, INF);
22     dis[1] =cnt[1]= 0; que.push (P (0, 1));
23     while (!que.empty()) {
24         P p = que.top();  que.pop();
25         int v = p.second;
26         if (dis[v] < p.first) continue;
27         for (int i = 0; i < G[v].size(); i++) {
28             edge e = G[v][i];
29             if (dis[e.to] > dis[v] + e.cost&&e.cost<=k*d) {
30                 dis[e.to] = dis[v] + e.cost;
31                 cnt[e.to]=min(cnt[e.to],cnt[v]+1);
32                 que.push (P (dis[e.to], e.to));
33             }
34         }
35     }
36     return cnt[n]<=k*e;
37 }
38 
39 int main(){
40     ios::sync_with_stdio(0);
41     cin.tie(0); cout.tie(0);
42 
43     cin>>n>>m>>c>>d>>e;
44     for(int i=0;i<m;i++){
45         int u,v,w; cin>>u>>v>>w;
46         addedge(u,v,w);
47         addedge(v,u,w);
48     }
49     int l=1, r=10000,mid;
50     while(l<r){
51         mid=(l+r)>>1;
52         if(dijkstra(mid)) r=mid;
53         else l=mid+1;
54     }
55     cout<<(long long)c*r<<endl;
56     return 0;
57 }