当我刚看到这道题的时候，我还奇怪这水题是怎么评上紫题的，两个限制条件，一个是温度，一个是距离，就是要我们找一条路径，路径上最高温度最小并且距离最短。贪心的想一想如果我们排好序加边，s、t连通之后跳出，显然这时的最高温度一定是最小的，和最小瓶颈生成树一个思想。当我们找到最小温度的时候，把比这个温度小的边加入图中跑最短路就行。复杂度为O(mlogn)，可以通过。
然而思路很简单，上手码就发现不简单了，虽然只需要码kruskal、并查集、dijkstra的板子，码出来也就20分钟，然而我却在debug上花了两个小时，一直以为是一些细节处理不对，后来仔细读题终于发现了关键的细节：这道题求的是s到t的路径。
路径（Path）：从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk，其中ei的顶点为vi及vi - 1，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。一条路径称为一简单路径(simple path)，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。
简单说，就是没有环。。。
所以我因为没有特判导致WA了11次qwq。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define N 200005 #define M 200005 using namespace std; struct Edge { int u,v; double r,d; }e[M]; int s,t; int head[N],nxt[M],to[M]; double val[M],dis[N]; #define inf 1e9 int n,m,cnt; double tem; void add(int u,int v,double d) { nxt[++cnt] = head[u]; head[u] = cnt; to[cnt] = v; val[cnt] = d; return; } bool cmp(Edge x,Edge y) { return x.r < y.r; } int fa[N],size[N]; void reset() { for(int i = 1;i <= n;i++) fa[i] = i,size[i] = 1; memset(e,0,sizeof(e)); memset(nxt,0,sizeof(nxt)); memset(to,0,sizeof(to)); memset(val,0,sizeof(val)); cnt = 0;tem = 0; memset(head,0,sizeof(head)); return; } int find(int x) { if(fa[x] != x) fa[x] = find(fa[x]); return fa[x]; } void merge(int x,int y) { x = find(x),y = find(y); if(size[x] < size[y]) swap(x,y); size[x] += size[y]; fa[y] = x; return; } void kruskal() { sort(e + 1,e + 1 + m,cmp); for(int i = 1;i <= m;i++) { int x = find(e[i].u),y = find(e[i].v); if(x != y) { merge(x,y); tem = max(tem,e[i].r); } if(find(s) == find(t)) break; } for(int j = 1;j <= m && e[j].r <= tem;j++) { add(e[j].u,e[j].v,e[j].d); add(e[j].v,e[j].u,e[j].d); } return; } struct Node { int u; double d; bool operator < (const Node &a) const { return d > a.d; } }top; priority_queue<Node>q; int path[N]; bool vis[N]; void dijkstra() { for(int i = 1;i <= n;i++) dis[i] = inf; dis[s] = 0; q.push((Node){s,0}); memset(path,0,sizeof(path)); memset(vis,0,sizeof(vis)); while(q.size()) { top = q.top(); q.pop(); int u = top.u; if(vis[u]) continue; vis[u] = 1;
for(int i = head[u];i;i = nxt[i]) { int v = to[i]; if(dis[v] > dis[u] + val[i]) { path[v] = u; dis[v] = dis[u] + val[i]; q.push((Node){v,dis[v]}); } } } return; } int st[N],toop; void print(int x) { toop = 0; memset(st,0,sizeof(st)); while(x) { st[++toop] = x; x = path[x]; } for(int i = toop;i >= 1;i--) { if(i != toop) printf(" "); printf("%d",st[i]); } return; } int main() { while(scanf("%d%d%d%d",&n,&m,&s,&t) != EOF) { reset(); for(int i = 1;i <= m;i++) scanf("%d%d%lf%lf",&e[i].u,&e[i].v,&e[i].r,&e[i].d); kruskal(); dijkstra(); print(t); printf(" %.1lf %.1lf ",dis[t],tem); } }