hud1548 a strange lift 最短路/bfs 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1548
题意:一个奇怪的电梯,每层楼的按键 只能上达 i + k[i] 层,下至 i- k[i] 层。不能到达超过n楼, 也不能小于 1楼。问最少按键数。以单个0结束输入。
思路:bfs, 从起点出发,每个楼层只会访问一次,在不出界的情况下访问能够到达的楼层。
总结:布吉岛神马原因,只有用G++交才过,导致我纠结了好多天,【摔】!
AC代码:
//AC
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<limits.h>
using namespace std;
#define maxn 2000
#define INF INT_MAX
int n, a, b;
int arr[maxn];
bool inq[maxn];
int dis[maxn]; void bfs(int st){
queue<int> q;
q.push(st);
int x;
dis[st] = ;
if(a < ||a > n||b < ||b > n) return;
while(!q.empty()){
x = q.front();
q.pop();
if(x < ||x > n||x == b) break;
if(x+arr[x] >= &&x+arr[x] <= n&&!inq[x+arr[x]]) { q.push(x+arr[x]); inq[x+arr[x]] = ; dis[x+arr[x]] = dis[x] + ; }
if(x-arr[x] >= &&x-arr[x] <= n&&!inq[x-arr[x]]) { q.push(x-arr[x]); inq[x-arr[x]] = ; dis[x-arr[x]] = dis[x] + ; }
//if(x+arr[x]>n&&x-arr[x]<1) break;
}
}
int main(){
while(~scanf("%d",&n) ,n){
scanf("%d%d", &a, &b);
for(int i = ; i <= n; i++)
scanf("%d",&arr[i]);
memset(inq, , sizeof(inq));
for(int i = ; i <= maxn; i++){
dis[i] = INF;
}
bfs(a);
printf("%d\n", (dis[b] == INF)?-:dis[b]);
}
}
hdu2544 最短路题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2544
题意:正如题目所说,是最短路,可以说是单源最短路入门题。
思路:可以用dijkstra做,这里我用spfa,不知道写的规不规范,总之思路和bellman-ford很像的,相当于Bellman-Ford的队列优化,也相当于做一趟bfs,具体是从当前节点出发,访问所有节点,如果能够到达,且被访问节点到起点的值比当前节点到起点的值加上当前节点到该节点大,则更新被访问的节点到起点的值,如果节点不在队列中,则入队,复杂度最坏是O(mn)。
总结:写完交wa了N+1次,最后才发现是INF的值没设好,Σ(っ °Д °;)っ设小了可能比更新后的距离小了,设大了,比如INT_MAX又溢出了。。。所以后来设成 节点数X单条路径最大距离 再大一点点就过了~~T^T
AC代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<limits.h>
#include<queue>
using namespace std;
#define maxn 109
#define INF 1000011
int n, m, w[maxn][maxn];
void spfa()
{
int d[maxn], k;
bool inq[maxn];
for(int i = ; i <= n; i++) {d[i] = INF; inq[i] = false;}
d[] = ;
//inq[1] = true;
queue<int> q;
q.push();
while(!q.empty()){
k = q.front(); q.pop();
inq[k] = false;
for(int j = ; j <= n; j++){
int t = d[k] + w[k][j];
if(d[j] > t){
d[j] = t;
if(!inq[j]){
q.push(j);
inq[j] = true;
}
}
}
}
printf("%d\n",d[n]);
} int main()
{
while(scanf("%d%d", &n, &m)&&n&&m){
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
w[i][j] = (i == j)?:INF; for(int i = ; i < m; i++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
w[a][b] = w[b][a] =c;
}
spfa();
}
return ;
}
hdu 3790 最短路径问题 基础最短路★
思路:基础最短路,先考虑路径再考虑费用
总结:WA原因, 输入时没考虑 a, b 之间存在多条路径
AC代码:
spfa版
//spfa版 #include<iostream>
#include<cstdio>
#include<cstring>
#include<limits.h>
#include<queue>
using namespace std;
#define maxn 2000
#define INF INT_MAX-100001
int n, m, a, b, d, p, s, t;
int w[maxn][maxn], cost[maxn][maxn];
struct node{
int dis, cos;
}; void test(node* x){
for(int i = ; i <= n; i++)
{
cout<<x[i].dis<<" "<<x[i].cos<<endl;
}
} void spfa(int s, int t)
{
node d[maxn]; bool inq[maxn]; memset(inq, , sizeof(inq));
int k;
for(int i = ; i < maxn; i++)
d[i].dis = d[i].cos = INF; d[s].dis = d[s].cos = ; inq[s] = true;
queue<int> q;
q.push(s);
while(!q.empty()){
k = q.front(); q.pop();
inq[k] = false;
for(int i = ; i <= n; i++){
if(i != k){
int t1 = d[k].dis + w[k][i]; int t2 = d[k].cos + cost[k][i];
if(t1 < d[i].dis){
d[i].dis = t1;
d[i].cos = t2;
if(!inq[i]) { q.push(i); inq[i] = true; }
}
if(t1 == d[i].dis&&t1 != INF){
if(t2 < d[i].cos) {
d[i].cos = t2;
}
if(!inq[i]){ q.push(i); inq[i] = true; }
}
}
}
}
//test(d);
printf("%d %d\n", d[t].dis, d[t].cos); }
void init()
{
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++){
w[i][j] = cost[i][j] = (i == j)?:INF;
}
}
int main()
{
while(scanf("%d%d", &n, &m),n,m){
init();
for(int i = ; i < m; i++){
scanf("%d%d%d%d", &a, &b, &d, &p);
if(d < w[a][b]){
w[a][b] = w[b][a] = d;
cost[a][b] = cost[b][a] = p;
}
}
scanf("%d%d", &s, &t); spfa(s, t);
}
return ;
}
dijkstra版
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#define maxn 1024
#define INF 0x3fffffff
using namespace std;
int n, m;
int d[maxn];
struct node{
int dis, cos;
};
node arr[maxn][maxn]; void test(int* c, int*d){
for(int i = ; i <= n; i++){
cout<<i<<" dis "<< c[i]<<" cost "<<d[i]<<endl;
}
} void dijkstra(int s, int t)
{
int d[maxn], cost[maxn];
bool vis[maxn];
memset(vis, false, sizeof(vis));
for(int i = ; i < maxn; i++)
d[i] = cost[i] = INF;
d[s] = cost[s] = ; for(int i = ; i <= n; i++){
int k, mm = INF; for(int j = ; j <= n; j++) if(!vis[j] && d[j] < mm) { mm = d[j]; k = j; }
vis[k] = true; for(int j = ; j <= n; j++){
if(d[j] > d[k] + arr[k][j].dis){
d[j] = d[k] + arr[k][j].dis;
cost[j] = cost[k] + arr[k][j].cos;
}
else if(d[j] < INF && d[j] == d[k] + arr[k][j].dis && cost[j] > cost[k] + arr[k][j].cos){
cost[j] = cost[k] + arr[k][j].cos;
}
}
}
//test(d, cost);
printf("%d %d\n", d[t], cost[t]);
} int main(){
while(scanf("%d%d", &n, &m) == &&(n||m)){
for(int i = ; i <= n; i++){
for(int j = ; j <= n; j++)
{
arr[i][j].dis = arr[i][j].cos = (i == j)?:INF;
}
}
for(int i = ; i < m; i++){
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
if(c < arr[a][b].dis){
arr[a][b].dis = arr[b][a].dis = c;
arr[a][b].cos = arr[b][a].cos = d;
}
}
int s, t;
scanf("%d%d", &s, &t);
dijkstra(s, t);
}
return ;
}
hdu 2066 一个人的旅行 【多源多汇,基础最短路】
思路:邻接表存图。 多源多汇,所以考虑建立【超级原点】,通常为0点,该点到所有起点的距离都为0,然后就是裸的最短路了。
总结:不知道为什么在自己电脑上init()之后s就被莫名其妙地改变成和t一个值了。。。。但是无改动用C++交上去过了,= =||,如果谁知道为神马请告诉我一声,涩涩~~~
AC代码如下:
//AC
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<limits.h>
#include<cstring>
using namespace std;
#define maxn 1010
#define INF INT_MAX-1000
struct node{
int v, wei;
};
vector<node> gra[maxn];
int t, s, d; int dis[maxn]; void init()
{
int i;
for(i = ; i <= maxn; i++)
gra[i].clear();
} void input()
{
for(int i = ; i < t; i++){
node re;
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
re.v = v; re.wei = w;
gra[u].push_back(re);
re.v = u;
gra[v].push_back(re);
}
for(int i = ; i < s; i++){
node re; re.wei = ;
scanf("%d", &re.v);
gra[].push_back(re);
int t = re.v; re.v = ;
gra[t].push_back(re);
}
} void output()
{
int ans = INF;
for(int i = ; i < d; i++){
int fina;
scanf("%d", &fina);
if(dis[fina] < ans) ans = dis[fina];
}
printf("%d\n", ans);
} void spfa()
{
bool inq[maxn]; memset(inq, , sizeof(inq));
for(int i = ; i < maxn; i++)
dis[i] = INF; queue<int> q;
q.push();
inq[] = true; dis[] = ;
while(!q.empty()){
int u = q.front(); q.pop();
inq[u] = false;
for(int i = ; i < gra[u].size(); i++){
int t = dis[u] + gra[u][i].wei;
int v = gra[u][i].v;
if(dis[v] > t){
dis[v] = t;
if(!inq[v]){
q.push(v);
inq[v] = true;
}
}
}
}
} int main()
{
while(scanf("%d%d%d", &t, &s, &d) != EOF){
init();
input();
spfa();
output();
}
return ;
}
同类型基础题如下:
1869 六度分离 Floyd最短路(water)
[原]最短路专题【基础篇】(updating...)的更多相关文章
-
[原]Java修炼 之 基础篇(二)Java语言构成
上次的博文中Java修炼 之 基础篇(一)Java语言特性我们介绍了一下Java语言的几个特性,今天我们介绍一下Java语言的构成. 所谓的Java构成,主要是指Java运行环境的组成, ...
-
个性二维码开源专题<;基础篇>;
二维码原理介绍: 二维码为什么是黑白相间的?黑色表示二进制的“1”,白色表示二进制的“0” “我们之所以对二维码进行扫描能读出那么多信息,就是因为这些信息被编入了二维码之中.”黄海平说,“制作二维码输 ...
-
[原]Java修炼 之 基础篇(一)Java语言特性
学习软件开发,首先要选择的就是选择需要采用的编程语言,考虑语言本身的优缺点和实际需求,综合评价之后选择相关的语言进行系统开发.本篇博客开始就从近年来比较流行的Java开始为大家讲起. 背景 1995年 ...
- Java面试专题-基础篇(1)
-
[C# 基础知识梳理系列]专题六:泛型基础篇——为什么引入泛型
引言: 前面专题主要介绍了C#1中的2个核心特性——委托和事件,然而在C# 2.0中又引入一个很重要的特性,它就是泛型,大家在平常的操作中肯定会经常碰到并使用它,如果你对于它的一些相关特性还不是很了解 ...
-
Java面试题之基础篇概览
Java面试题之基础篇概览 1.一个“.java”源文件中是否可以包含多个类(不是内部类)?有什么限制? 可以有多个类,但只能有一个public的类,且public的类名必须与文件名相一致. 2.Ja ...
-
java学习笔记-基础篇
Java基础篇 1—12 常识 13 this关键字 14参数传递 16 继承 17 访问权限 28—31异常 1—12 常识 1.文件夹以列表展示,显示扩展名,在地址栏显示全路径 2.javac编译 ...
-
小白—职场之Java基础篇
java基础篇 java基础 目录 1.java是一种什么语言,jdk,jre,jvm三者的区别 2.java 1.5之后的三大版本 3.java跨平台及其原理 4.java 语言的特点 5.什么是字 ...
-
Asp.Net Core基础篇之:白话管道中间件
在Asp.Net Core中,管道往往伴随着请求一起出现.客户端发起Http请求,服务端去响应这个请求,之间的过程都在管道内进行. 举一个生活中比较常见的例子:旅游景区. 我们都知道,有些景区大门离景 ...
随机推荐
-
多线程、委托、Invoke解决winform界面卡死的问题,并带开关
一.知识点介绍 1,更新控件的内容,应该调用控件的Invoke方法. Invoke指: 在拥有控件的基础窗口句柄的线程上,用指定的参数列表执行指定委托.该方法接收一个委托类型和委托的参数,因此需要定义 ...
-
如何破解mac版UltraEdit?
Rodolfo教你如何破解UtralEdit? 第一步:去官网下载原载,先运行一次: 第二步:在终端里执行下面代码就可以破解完成!printf '\x31\xC0\xFF\xC0\xC3\x90' | ...
-
ArrayList和Hashtable
public class Tools{ public string Name{get ;set;}} #region 0.1ArrayList集合 ////告诉内存,我要存储内容 //ArrayLis ...
-
解析PHP中的file_get_contents获取远程页面乱码的问题【转】
在工作中,遇到一个问题.我需要将一个网址(该网址是一个json数据的接口,即 打开该网址,在浏览器中显示的是json数据),我使用file_get_contents($url),数据是乱码的. 通过查 ...
-
HDU 2296 Ring [AC自动机 DP 打印方案]
Ring Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submissio ...
-
es6学习笔记-proxy对象
前提摘要 尤大大的vue3.0即将到来,虽然学不动了,但是还要学的啊,据说vue3.0是基于proxy来进行对值进行拦截并操作,所以es6的proxy也是要学习一下的. 一 什么是proxy Prox ...
-
laravel上传图片报错
在laravel的上传图片代码文件中路径如下: vendor\stevenyangecho\laravel-u-editor\src\Uploader\Upload.php第131行有一句代码错误$r ...
-
C#游戏开发中快速的游戏循环
C#游戏开发中快速的游戏循环的实现.参考<精通C#游戏编程>一书. using System; using System.Collections.Generic; using System ...
-
P1828 香甜的黄油 Sweet Butter
对于这道洛谷ac而我整了一下午的codevs的题,我也是很绝望啊. 原因是队列数组开小了我勒个去???我说STL怎么能过 题目描述 农夫John发现做出全威斯康辛州最甜的黄油的方法:糖.把糖放在一片牧 ...
-
oracle存储过程结合我公司代码1
1. Framework.QueryInfo info1 = new Framework.QueryInfo(); //string Sql = Holwor ...