uva 10816(二分+Dijkstra)

题意：在一张图中会有重边，然后每条边上有两个权值，一个温度一个距离，让你找一条温度的最小瓶颈路，让这条最小瓶颈路距离最短。

思路：二分温度，然后用Dijkstra判断，最后输出答案。虽然想到思路后很简单，但是我一开始没注意看会有重边所以错了好多次。

代码如下：

  1 /**************************************************
  2  * Author     : xiaohao Z
  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
  4  * Last modified : 2014-02-06 12:38
  5  * Filename     : uva_10816.cpp
  6  * Description     : 
  7  * ************************************************/
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <cmath>
 14 #include <algorithm>
 15 #include <queue>
 16 #include <stack>
 17 #include <vector>
 18 #include <set>
 19 #include <map>
 20 #define MP(a, b) make_pair(a, b)
 21 #define PB(a) push_back(a)
 22 
 23 using namespace std;
 24 typedef long long ll;
 25 typedef pair<int, int> pii;
 26 typedef pair<unsigned int,unsigned int> puu;
 27 typedef pair<int, double> pid;
 28 typedef pair<double, int> pdi;
 29 typedef pair<ll, int> pli;
 30 typedef pair<int, ll> pil;
 31 
 32 const int INF = 0x3f3f3f3f;
 33 const double eps = 1E-6;
 34 const int LEN = 110;
 35 struct P{
 36     int v;
 37     double t, d;
 38 };
 39 vector<P> Map[LEN];
 40 int n, m, st, ed, pre[LEN];
 41 double dis[LEN];
 42 
 43 struct cmp{
 44     bool operator() (pdi a, pdi b){ return a.first > b.first;}
 45 };
 46 
 47 P M_P(int a, double b, double c){
 48      P ret;ret.v = a, ret.d = b, ret.t = c;return ret;
 49 }
 50 
 51 double Dijkstra(int vex, double tt){
 52     priority_queue<pdi, vector<pdi>, cmp> q;
 53     int vis[LEN] = {0};
 54     for(int i=0; i<LEN; i++) dis[i] = INF;
 55     memset(pre, 0, sizeof pre);
 56     dis[vex] = 0;
 57     pre[vex] = -1;
 58     q.push(MP(dis[vex], vex));
 59     while(!q.empty()){
 60         pdi nvex = q.top();q.pop();
 61         int nv = nvex.second;
 62         if(vis[nv]) continue;
 63         vis[nv] = 1;
 64         for(int i=0; i<Map[nv].size(); i++){
 65             int x = Map[nv][i].v;
 66                double y = Map[nv][i].d;
 67             if(dis[x] > dis[nv] + y && Map[nv][i].t<=tt){
 68                  dis[x] = dis[nv] + y;
 69                  pre[x] = nv;
 70                  q.push(MP(dis[x], x));
 71             }
 72         }
 73     }
 74     return dis[ed];
 75 }
 76 
 77 void out(int v){
 78      if(pre[v] < 0){
 79          printf("%d", v);
 80          return ;
 81      }
 82      out(pre[v]);
 83      printf(" %d", v);
 84 }
 85 
 86 int main()
 87 {
 88 //    freopen("in.txt", "r", stdin);
 89 
 90     int a, b;
 91     double c, d;
 92     while(scanf("%d%d", &n, &m)!=EOF){
 93         for(int i=0; i<LEN; i++)Map[i].clear();
 94         scanf("%d%d", &st, &ed);
 95         double l = INF, r = 0, ans;
 96         for(int i=0; i<m; i++){
 97             scanf("%d%d%lf%lf", &a, &b, &c, &d);
 98             Map[a].PB(M_P(b, d, c));
 99             Map[b].PB(M_P(a, d, c));
100             l = min(l, c);
101             r = max(r, c);
102         }
103         while(r-l > eps){
104             double m = (l+r)/2;
105             double ta = Dijkstra(st, m);
106             if(ta != INF) r = m;
107             else l = m;
108          }
109         ans = Dijkstra(st, r);
110         out(ed);puts("");
111         printf("%.1lf %.1lf
", ans, r);
112     }
113     return 0;
114 }

View Code

奔跑吧！少年！趁着你还年轻