题意：
给出 一个图
点与点之间的路径上有两个权值 路径长度和温度
要求在所走路径中的温度的最大值最小的前提下 走最短路径
解题思路1：
首先用 最小生成树 的方法走出 最小瓶颈路 。把在这期间用到的全部温度小于 路径上最大温度 的边存下来，作为接下来求最短路径的图。
在新生成的图中求最短路径就可以；
code
#include#include #include #include #include using namespace std;const int maxm = 10005;const int maxn = 105;struct Edge{ int u,v; double dist,tm; void read(){ scanf("%d%d%lf%lf",&u,&v,&tm,&dist); u--;v--; } bool operator<(const Edge et)const{ if(tm != et.tm) return tm < et.tm; else return dist < et.dist; }}e[maxm];int n,m,s,t;int parent[maxn];vector g[maxn];void init(){ scanf("%d%d",&s,&t); s--;t--; for(int i = 0; i < m; i++){ e[i].read(); } for(int i = 0; i < n; i++){ g[i].clear(); }}int find(int x){ if(parent[x] == x) return x; else return parent[x] = find(parent[x]);}const int INF = 0x3f3f3f3f;const int MAXNODE = 105;struct Edge2 { int u, v; double dist; Edge2() {} Edge2(int u, int v, double dist) { this->u = u; this->v = v; this->dist = dist; }};struct HeapNode { double d; int u; HeapNode() {} HeapNode(double d, int u) { this->d = d; this->u = u; } bool operator < (const HeapNode& c) const { return d > c.d; }};struct Dijkstra { int n, m; vector edges; vector g[MAXNODE]; bool done[MAXNODE]; double d[MAXNODE]; int p[MAXNODE]; void init(int tot) { n = tot; for (int i = 0; i < n; i++) g[i].clear(); edges.clear(); } void add_Edge(int u, int v, double dist) { edges.push_back(Edge2(u, v, dist)); m = edges.size(); g[u].push_back(m - 1); } void print(int s, int e) {//shun xu if (s == e) { printf("%d", e + 1); return; } print(s, edges[p[e]].u); printf(" %d", e + 1); } void print2(int s, int e) {//ni xu if (s == e) { printf("%d", e + 1); return; } printf("%d ", e + 1); print2(s, edges[p[e]].u); } void dijkstra(int s) { priority_queue Q; for (int i = 0; i < n; i++) d[i] = INF*1.0; d[s] = 0.0; memset(done, false, sizeof(done)); Q.push(HeapNode(0, s)); while (!Q.empty()) { HeapNode x = Q.top(); Q.pop(); int u = x.u; if (done[u]) continue; done[u] = true; for (int i = 0; i < g[u].size(); i++) { Edge2& e = edges[g[u][i]]; if (d[e.v] > d[u] + e.dist) { d[e.v] = d[u] + e.dist; p[e.v] = g[u][i]; Q.push(HeapNode(d[e.v], e.v)); } } } }} graph;void solve(){// printf("...\n"); double ans = 0; sort(e,e+m);// for(int i = 0; i < m; i++){// printf("%.1lf %.1lf %d %d\n",e[i].dist,e[i].tm,e[i].u,e[i].v);// } for(int i = 0; i < n; i++) parent[i] = i; double max_tm = 500.0; graph.init(n); for(int i = 0; i < m; i++){ if(e[i].tm > max_tm) break; graph.add_Edge(e[i].u,e[i].v,e[i].dist); graph.add_Edge(e[i].v,e[i].u,e[i].dist); int pu = find(e[i].u); int pv = find(e[i].v); if(pu == pv) continue; parent[pu] = pv; if(find(s) == find(t)){ max_tm = e[i].tm; } } graph.dijkstra(s); graph.print(s,t); printf("\n"); printf("%.1lf %.1lf\n",graph.d[t],max_tm);}int main(){ while(scanf("%d%d",&n,&m) != EOF){ init(); solve(); } return 0;}
解题思路二：
把原图存下来，然后二分温度，再把全部小于温度mid的边拿出来构成一个新图，然后继续dijkstra求最短路，有成功和不成功两种结果，找到能成功的最小温度就可以
code
#include二分在非常多情况下都是非常好用的一种方法~#include #include #include using namespace std;const int MAXNODE = 105;const int MAXEDGE = 20005;typedef double Type;const Type INF = 0x3f3f3f3f;struct Edge { int u, v; Type dist, d; Edge() {} Edge(int u, int v, Type dist, Type d = 0) { this->u = u; this->v = v; this->dist = dist; this->d = d; } void read() { scanf("%d%d%lf%lf", &u, &v, &d, &dist); u--; v--; }};struct HeapNode { Type d; int u; HeapNode() {} HeapNode(Type d, int u) { this->d = d; this->u = u; } bool operator < (const HeapNode& c) const { return d > c.d; }};int n, m, s, t;struct Dijkstra { int n, m; Edge edges[MAXEDGE]; int first[MAXNODE]; int next[MAXEDGE]; bool done[MAXNODE]; Type d[MAXNODE]; int p[MAXNODE]; void init(int n) { this->n = n; memset(first, -1, sizeof(first)); m = 0; } void add_Edge(int u, int v, Type dist) { edges[m] = Edge(u, v, dist); next[m] = first[u]; first[u] = m++; } void add_Edge(Edge e) { edges[m] = e; next[m] = first[e.u]; first[e.u] = m++; } void print(int e) {//shun xu if (p[e] == -1) { printf("%d", e + 1); return; } print(edges[p[e]].u); printf(" %d", e + 1); } void print2(int e) {//ni xu if (p[e] == -1) { printf("%d\n", e + 1); return; } printf("%d ", e + 1); print2(edges[p[e]].u); } bool dijkstra(int s, int t) { priority_queue Q; for (int i = 0; i < n; i++) d[i] = INF; d[s] = 0; p[s] = -1; memset(done, false, sizeof(done)); Q.push(HeapNode(0, s)); while (!Q.empty()) { HeapNode x = Q.top(); Q.pop(); int u = x.u; if (u == t) return true; if (done[u]) continue; done[u] = true; for (int i = first[u]; i != -1; i = next[i]) { Edge& e = edges[i]; if (d[e.v] > d[u] + e.dist) { d[e.v] = d[u] + e.dist; p[e.v] = i; Q.push(HeapNode(d[e.v], e.v)); } } } return false; }} gao;Edge e[MAXEDGE];bool judge(double mid) { gao.init(n); for (int i = 0; i < m; i++) { if (e[i].d > mid) continue; gao.add_Edge(e[i]); gao.add_Edge(Edge(e[i].v, e[i].u, e[i].dist, e[i].d)); } if (gao.dijkstra(s, t)) return true; return false;}int main() { while (~scanf("%d%d", &n, &m)) { scanf("%d%d", &s, &t); s--; t--; for (int i = 0; i < m; i++) e[i].read(); double l = 0, r = 50, mid; while (r - l > 1e-8) { mid = (l + r) / 2; if (judge(mid)) r = mid; else l = mid; } if (judge(r)) { gao.print(t); printf("\n"); printf("%.1lf %.1lf\n", gao.d[t], mid); } } return 0;}