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 105
struct xxx{
int high;
int low;
}x[10005];
struct son{
int v;
int w;
};
vector<son> g[M];
int dist[M], n, H[M];
bool inq[M];
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[i] = inf;
inq[i] = false;
}
queue<int> q;
q.push (u);
dist[u] = 0;
inq[u] = true;
while (!q.empty())
{
u = q.front();
q.pop();
inq[u] = false;
if (H[u] < low || H[u] > high) //起点也要限制
continue;
for (i = 0; i < g[u].size(); i++)
{
v = g[u][i].v;
if (H[v] < low || H[v] > high) //高度的限制
continue;
w = g[u][i].w;
if (dist[u] + w < dist[v])
{
dist[v] = dist[u] + w;
if (!inq[v])
{
q.push (v);
inq[v] = 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[i].clear();
}
k = 0;
for (i = 1; i <= n; i++)
{
for (j = i; j <= n; j++) //不能写成j=i+1,想想起点=终点的情况
{
x[k].low = min (H[i], H[j]);
x[k++].high = max (H[i], H[j]);
}
}
while (m--)
{
scanf ("%d%d%d", &u, &v, &w);
s.v = v;
s.w = w;
g[u].push_back (s);
s.v = u;
g[v].push_back (s);
}
sort (x, x+k, cmp); //按差排序
for (i = 0; i < k; i++) //差从小到大暴力枚举
{
spfa (x[i].low, x[i].high);
if (dist[n] != inf) //一旦可到达,立刻得出答案
break;
}
printf ("%d %d\n", x[i].high-x[i].low, dist[n]);
}
return 0;
}
分享到:
相关推荐
最短路(HDU-2544).rar
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
HDU最全ac代码
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1695 GCD(欧拉函数+容斥原理).docx
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码