优先队列的使用:
- include<queue>// 关联头文件
- struct node{
- int x,y;
- friend bool operator <(node d1,node d2)
- {
- return d1.x>d2.x;
- }// 定义优先队列运算规则必须
- }
- // 程序里
- priority_queue<node> q;// 定义优先队列
- node cur,next;
- q.push(cur);//push
- !q.empty// 队列非空
- cur=q.pop();// 弹出
- next=q.top();// 队首元素
加广搜:
压的时候一层层压, 队列非空时一个个弹出, 节点也带上它的层数就好了
Catch That Cow
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 * X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
贴代码:
- #include<iostream>
- #include<cstdio>
- #include<queue>
- using namespace std;
- int num,k;
- bool visit[200010];
- priority_queue<node> q;
- struct node{
- int d,n;
- friend bool operator <(node n1,node n2)
- {
- return n1.d> n2.d;
- }
- };
- int bfs()
- {
- node cur,next;
- cur.n=num;
- cur.d=0;
- q.push(cur); visit[cur.n]=1;
- while (!q.empty())
- {
- cur=q.top();
- q.pop();
- if (cur.n==k)
- {
- return cur.d;
- }
- next.n=cur.n+1;
- next.d=cur.d+1;
- if (next.n<200000 and next.n>0 and visit[next.n]==0) { q.push(next); visit[next.n]=1; }
- next.n=cur.n-1;
- if (next.n<200000 and next.n>0 and visit[next.n]==0) { q.push(next); visit[next.n]=1; }
- next.n=cur.n*2;
- if (next.n<200000 and next.n>0 and visit[next.n]==0) { q.push(next); visit[next.n]=1; }
- }
- return 0;
- }
- int main()
- {
- cin>>num>>k;
- for (int i=1;i<=k;i++)
- visit[i]=false;
- if (num>k)
- cout<<num-k;
- else
- cout<<bfs();
- return 0;
- }
vector 的使用:// 转载自 CSDN
vector 是 C++ STL 的一个重要成员, 使用它时需要包含头文件:
#include<vector>
一, vector 的初始化: 可以有五种方式, 举例说明如下:
- (1) vector<int> a(10); // 定义了 10 个整型元素的向量(尖括号中为元素类型名, 它可以是任何合法的数据类型), 但没有给出初值, 其值是不确定的.
- (2)vectora(10,1); // 定义了 10 个整型元素的向量, 且给出每个元素的初值为 1
- (3)vectora(b); // 用 b 向量来创建 a 向量, 整体复制性赋值
- (4)vectora(b.begin(),b.begin+3); // 定义了 a 值为 b 中第 0 个到第 2 个 (共 3 个) 元素
- (5)int b[7]={
- 1,2,3,4,5,9,8
- };
- vectora(b,b+7); // 从数组中获得初值
二, vector 对象的几个重要操作, 举例说明如下:
- (1)a.assign(b.begin(), b.begin()+3); //b 为向量, 将 b 的 0~2 个元素构成的向量赋给 a
- (2)a.assign(4,2); // 是 a 只含 4 个元素, 且每个元素为 2
- (3)a.back(); // 返回 a 的最后一个元素
- (4)a.front(); // 返回 a 的第一个元素
- (5)a[i]; // 返回 a 的第 i 个元素, 当且仅当 a[i]存在 2013-12-07
- (6)a.clear(); // 清空 a 中的元素
- (7)a.empty(); // 判断 a 是否为空, 空则返回 ture, 不空则返回 false
- (8)a.pop_back(); // 删除 a 向量的最后一个元素
- (9)a.erase(a.begin()+1,a.begin()+3); // 删除 a 中第 1 个 (从第 0 个算起) 到第 2 个元素, 也就是说删除的元素从 a.begin()+1 算起 (包括它) 一直到 a.begin()+ 3(不包括它)
- (10)a.push_back(5); // 在 a 的最后一个向量后插入一个元素, 其值为 5
- (11)a.insert(a.begin()+1,5); // 在 a 的第 1 个元素 (从第 0 个算起) 的位置插入数值 5, 如 a 为 1,2,3,4, 插入元素后为 1,5,2,3,4
- (12)a.insert(a.begin()+1,3,5); // 在 a 的第 1 个元素 (从第 0 个算起) 的位置插入 3 个数, 其值都为 5
- (13)a.insert(a.begin()+1,b+3,b+6); //b 为数组, 在 a 的第 1 个元素 (从第 0 个算起) 的位置插入 b 的第 3 个元素到第 5 个元素(不包括 b+6), 如 b 为 1,2,3,4,5,9,8 , 插入元素后为 1,4,5,9,2,3,4,5,9,8
- (14)a.size(); // 返回 a 中元素的个数;
- (15)a.capacity(); // 返回 a 在内存中总共可以容纳的元素个数
- (16)a.resize(10); // 将 a 的现有元素个数调至 10 个, 多则删, 少则补, 其值随机
- (17)a.resize(10,2); // 将 a 的现有元素个数调至 10 个, 多则删, 少则补, 其值为 2
- (18)a.reserve(100); // 将 a 的容量 (capacity) 扩充至 100, 也就是说现在测试 a.capacity(); 的时候返回值是 100. 这种操作只有在需要给 a 添加大量数据的时候才 显得有意义, 因为这将避免内存多次容量扩充操作(当 a 的容量不足时电脑会自动扩容, 当然这必然降低性能)
- (19)a.swap(b); //b 为向量, 将 a 中的元素和 b 中的元素进行整体性交换
- (20)a==b; //b 为向量, 向量的比较操作还有!=,>=,<=,>,<三, 顺序访问 vector 的几种方式, 举例说明如下:
(1)向量 a 中添加元素
- vectora;
- for(int i=0;i<10;i++)
- a.push_back(i);
2, 也可以从数组中选择元素向向量中添加
- int a[6]={
- 1,2,3,4,5,6
- };
- vectorb;
- for(int i=1;i<=4;i++)
- b.push_back(a[i]);
3, 也可以从现有向量中选择元素向向量中添加
- int a[6]={
- 1,2,3,4,5,6
- };
- vectorb;
- vectorc(a,a+4);
- for(vector::iterator it=c.begin();it<c.end();it++)
- b.push_back(*it);
4, 也可以从文件中读取元素向向量中添加
- ifstream in("data.txt");
- vectora;
- for(int i; in>>i)
- a.push_back(i);
5,[误区]
- vectora;
- for(int i=0;i<10;i++)
- a[i]=i;
- // 这种做法以及类似的做法都是错误的. 刚开始我也犯过这种错误, 后来发现, 下标只能用于获取已存在的元素, 而现在的 a[i]还是空的对象
(2)从向量中读取元素
1, 通过下标方式读取
- int a[6]={
- 1,2,3,4,5,6
- };
- vectorb(a,a+4);
- for(int i=0;i<=b.size()-1;i++)
- cout<<b[i]<<" ";
2, 通过遍历器方式读取
- int a[6]={
- 1,2,3,4,5,6
- };
- vectorb(a,a+4);
- for(vector::iterator it=b.begin();it!=b.end();it++)
- cout<<*it<<" ";
四, 几种重要的算法, 使用时需要包含头文件:
- #include<algorithm>
- (1)sort(a.begin(),a.end()); // 对 a 中的从 a.begin()(包括它)到 a.end()(不包括它)的元素进行从小到大排列
- (2)reverse(a.begin(),a.end()); // 对 a 中的从 a.begin()(包括它)到 a.end()(不包括它)的元素倒置, 但不排列, 如 a 中元素为 1,3,2,4, 倒置后为 4,2,3,1
- (3)copy(a.begin(),a.end(),b.begin()+1); // 把 a 中的从 a.begin()(包括它)到 a.end()(不包括它)的元素复制到 b 中, 从 b.begin()+1 的位置 (包括它) 开始复制, 覆盖掉原有元素
- (4)find(a.begin(),a.end(),10); // 在 a 中的从 a.begin()(包括它)到 a.end()(不包括它)的元素中查找 10, 若存在返回其在向量中的位置
- ----------------
- #include<iostream>
- #include<cstdio>
- #include<vector>
- #include<queue>
- using namespace std;
- struct node{
- int num,dep;
- };
- vector <int> a[10010];
- int tot;
- void bfs(int n)
- {
- int maxx=0,minn=20000;
- bool visit[10010];
- queue<node> q;
- node cur,next;
- for (int i=1;i<=tot;i++)
- visit[i]=0;
- cur.dep=1;
- cur.num=n;
- visit[n]=1;
- q.push(cur);
- while (!q.empty())
- {
- cur=q.front();
- q.pop();
- for (int i=1;i<=a[cur.num].size();i++)
- {
- if (visit[a[cur.num][i-1]]==0)
- {
- visit[a[cur.num][i-1]]=1;
- next.num=a[cur.num][i-1];
- next.dep=cur.dep+1;
- q.push(next);
- }
- if (next.dep==maxx)
- minn=min(minn,next.num);
- if (next.dep>maxx)
- {
- maxx=next.dep;
- minn=next.num;
- }
- }
- }
- if (maxx==0)
- cout<<0<<endl;
- else
- cout<<minn<<endl;
- }
- int main()
- {
- // freopen("test.in","r",stdin);
- // freopen("test.out","w",stdout);
- int m,k,u,v,x;
- cin>>tot>>m>>k;
- for (int i=1;i<=m;i++)
- {
- cin>>u>>v;
- a[u].push_back(v);
- a[v].push_back(u);
- }
- for (int i=1;i<=k;i++)
- {
- cin>>x;
- bfs(x);
- }
- }
来源: http://www.bubuko.com/infodetail-3298274.html