题意:在一张图中会有重边,然后每条边上有两个权值,一个温度一个距离,让你找一条温度的最小瓶颈路,让这条最小瓶颈路距离最短。
思路:二分温度,然后用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\n", ans, r); 112 } 113 return 0; 114 }