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

灰太狼 2021-03-30 12:05 437阅读 0赞

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

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

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

#include <bits/stdc++.h>
     using namespace std;
     #define INF 0x3f3f3f3f
     #define MAXN 100050
     typedef pair<int, int> P;
     
     struct edge { int to, cost;
         edge (int too, int costt) { to = too; cost = costt; }
     };
     vector <edge> G[MAXN];
     void addedge (int u, int v, int w) {
         G[u].push_back (edge (v, w));
     }
     
     int dis[MAXN], cnt[MAXN];
     int n, m,c,d,e;
     
     bool dijkstra (int k) {
         priority_queue<P, vector<P>, greater<P> > que;
         fill (dis, dis + n + 1, INF);
         fill (cnt,cnt+n+1, INF);
         dis[1] =cnt[1]= 0; que.push (P (0, 1));
         while (!que.empty()) {
             P p = que.top();  que.pop();
             int v = p.second;
             if (dis[v] < p.first) continue;
             for (int i = 0; i < G[v].size(); i++) {
                 edge e = G[v][i];
                 if (dis[e.to] > dis[v] + e.cost&&e.cost<=k*d) {
                     dis[e.to] = dis[v] + e.cost;
                     cnt[e.to]=min(cnt[e.to],cnt[v]+1);
                     que.push (P (dis[e.to], e.to));
                 }
             }
         }
         return cnt[n]<=k*e;
     }
     
     int main(){
         ios::sync_with_stdio(0);
         cin.tie(0); cout.tie(0);
     
         cin>>n>>m>>c>>d>>e;
         for(int i=0;i<m;i++){
             int u,v,w; cin>>u>>v>>w;
             addedge(u,v,w);
             addedge(v,u,w);
         }
         int l=1, r=10000,mid;
         while(l<r){
             mid=(l+r)>>1;
             if(dijkstra(mid)) r=mid;
             else l=mid+1;
         }
         cout<<(long long)c*r<<endl;
         return 0;
     }