【枚举+最短路】HDU 2363 Cycling
http://acm.hdu.edu.cn/showproblem.php?pid=2363题意：求最小高度差下的最短路
#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>//#include <map>#include <queue>#include <utility>#include <iomanip>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>//#include <ctime>#include <ctype.h>using namespace std;#define LL __int64#define inf 0x3fffffff#define M 105struct xxx{ int high; int low;}x;struct son{ int v; int w;};vector<son> g;int dist, n, H;bool inq;bool cmp (xxx a, xxx b){ return (a.high - a.low) < (b.high - b.low);}void spfa (int low, int high){ int i, v, w, u = 1; for (i = 1; i <= n; i++) { dist = inf; inq = false; } queue<int> q; q.push (u); dist = 0; inq = true; while (!q.empty()) { u = q.front(); q.pop(); inq = false; if (H < low || H > high) //起点也要限制 continue; for (i = 0; i < g.size(); i++) { v = g.v; if (H < low || H > high) //高度的限制 continue; w = g.w; if (dist + w < dist) { dist = dist + w; if (!inq) { q.push (v); inq = true; } } } }}int main(){ int t, m, u, v, w, i, j, k; son s; scanf ("%d", &t); while (t--) { scanf ("%d%d", &n, &m); for (i = 1; i <= n; i++) { scanf ("%d", H+i); g.clear(); } k = 0; for (i = 1; i <= n; i++) { for (j = i; j <= n; j++) //不能写成j=i+1，想想起点=终点的情况 { x.low = min (H, H); x.high = max (H, H); } } while (m--) { scanf ("%d%d%d", &u, &v, &w); s.v = v; s.w = w; g.push_back (s); s.v = u; g.push_back (s); } sort (x, x+k, cmp); //按差排序 for (i = 0; i < k; i++) //差从小到大暴力枚举 { spfa (x.low, x.high); if (dist != inf) //一旦可到达，立刻得出答案 break; } printf ("%d %d\n", x.high-x.low, dist); } return 0;}
页:
[1]