题意：
给出 一个图
点与点之间的路径上有两个权值 路径长度和温度
要求在所走路径中的温度的最大值最小的前提下 走最短路径
解题思路1：
首先用 最小生成树 的方法走出 最小瓶颈路 ，把在这期间用到的所有温度小于 路径上最大温度 的边存下来，作为接下来求最短路径的图；
在新生成的图中求最短路径即可；
code
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<queue>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<Edge> 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<Edge2> edges;vector<int> 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 xuif (s == e) {printf("%d", e + 1);return;}print(s, edges[p[e]].u);printf(" %d", e + 1);}void print2(int s, int e) {//ni xuif (s == e) {printf("%d", e + 1);return;}printf("%d ", e + 1);print2(s, edges[p[e]].u);}void dijkstra(int s) {priority_queue<HeapNode> 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 <cstdio>#include <cstring>#include <vector>#include <queue>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 xuif (p[e] == -1) {printf("%d", e + 1);return;}print(edges[p[e]].u);printf(" %d", e + 1);}void print2(int e) {//ni xuif (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<HeapNode> 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;}二分在很多情况下都是很好用的一种方法~
偶尔被惊鸿一瞥的美丽吸引;或者走进一条深沉深沉的巷道，
