由于要同时满足两个条件，优先满足温度最低，其次是距离最短。 于是按照温度建最小生成树，然后把低于最高温度的边都加进来，spfa找距离最短的路线就可以了。
#include<iostream> #include<string> #include<cstdio> #include<set> #include<stack> #include<list> #include<vector> #include<queue> #include<algorithm> #include<cstring> #include<cmath> #include<fstream> using namespace std; typedef long long ll; const int maxn = 110,maxe = 10010,INF = 0x3f3f3f3f; int n,m,st,ed; struct node{ int u,v; double tem,len; bool operator < (const node &a) const{ return tem < a.tem; } }e[maxe]; int top[maxn]; int find(int x){ if (x == top[x]) return x; else return top[x] = find(top[x]); } double kruskal(){ for(int i = 1;i <= n;++i) top[i] = i; int k = 0; double tem = 0; while(find(st) != find(ed)){ int u = find(e[k].u),v = find(e[k].v); tem = e[k].tem; if (u != v){ top[u] = v; } k++; } return tem; } vector<pair<int,double>> r[maxn]; vector<int> path; double spfa(){ queue<int> Q; int fa[maxn] = {}; bool inQ[maxn] = {}; double d[maxn]; for(int i = 1;i <= n;++i) d[i] = INF; d[st] = 0; inQ[st] = 1; Q.push(st); while(!Q.empty()){ int u = Q.front();Q.pop(); inQ[u] = 0; for(int i = 0;i < r[u].size();++i){ int v = r[u][i].first; double len = r[u][i].second; if (d[v] > d[u] + len){ d[v] = d[u] + len; fa[v] = u; if (!inQ[v]){ Q.push(v); inQ[v] = 1; } } } } path.clear(); int x = ed; while(x != st){ path.push_back(x); x = fa[x]; } path.push_back(st); reverse(path.begin(),path.end()); return d[ed]; } void init(){ for(int i = 1;i <= n;++i) r[i].clear(); cin >> st >> ed; for(int i = 0;i < m;++i) cin >> e[i].u >> e[i].v >> e[i].tem >> e[i].len; sort(e,e + m); double mxtem = kruskal(); for(int i = 0;i < m;++i){ if (e[i].tem > mxtem) continue; int u = e[i].u,v = e[i].v; double len = e[i].len; r[u].push_back({v,len}); r[v].push_back({u,len}); } double mxlen = spfa(); for(int i = 0;i < path.size();++i){ if (i) printf(" "); printf("%d",path[i]); } printf("\n%.1f %.1f\n",mxlen,mxtem); } int main(){ while(cin >> n >> m){ init(); } }