優先佇列的使用：
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）vector
（3）vector
（4）vector
（5）int b[7]={1,2,3,4,5,9,8};
vector
二、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中添加元素
vector
for(int i=0;i<10;i++)
a.push_back(i);
2、也可以從陣列中選擇元素向向量中添加
int a[6]={1,2,3,4,5,6};
vector
for(int i=1;i<=4;i++)
b.push_back(a[i]);
3、也可以從現有向量中選擇元素向向量中添加
int a[6]={1,2,3,4,5,6};
vector
vector
for(vector
b.push_back(*it);
4、也可以從檔案中讀取元素向向量中添加
ifstream in("data.txt");
vector
for(int i; in>>i)
a.push_back(i);
5、【誤區】
vector
for(int i=0;i<10;i++)
a[i]=i;
//這種做法以及類似的做法都是錯誤的，剛開始我也犯過這種錯誤，后來發現，下標只能用于獲取已存在的元素，而現在的a[i]還是空的物件
（2）從向量中讀取元素
1、通過下標方式讀取
int a[6]={1,2,3,4,5,6};
vector
for(int i=0;i<=b.size()-1;i++)
cout<<b[i]<<" ";
2、通過遍歷器方式讀取
int a[6]={1,2,3,4,5,6};
vector
for(vector
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，若存在回傳其在向量中的位置
————————————————
著作權宣告：本文為CSDN博主「qinyuehong」的原創文章，遵循 CC 4.0 BY-SA 著作權協議，轉載請附上原文出處鏈接及本宣告，
原文鏈接：https://blog.csdn.net/qinyuehong/article/details/92837359
于是有了下面的題目：
喊山
一個山頭呼喊的聲音可以被臨近的山頭同時聽到，題目假設每個山頭最多有兩個能聽到它的臨近山頭，給定任意一個發出原始信號的山頭，本題請你找出這個信號最遠能傳達到的地方，
輸入格式：
輸入第一行給出3個正整數n、m和k，其中n（≤10000）是總的山頭數（于是假設每個山頭從1到n編號），接下來的m行，每行給出2個不超過n的正整數，數字間用空格分開，分別代表可以聽到彼此的兩個山頭的編號，這里保證每一對山頭只被輸入一次，不會有重復的關系輸入，最后一行給出k（≤10）個不超過n的正整數，數字間用空格分開，代表需要查詢的山頭的編號，
輸出格式：
依次對于輸入中的每個被查詢的山頭，在一行中輸出其發出的呼喊能夠連鎖傳達到的最遠的那個山頭，注意：被輸出的首先必須是被查詢的個山頭能連鎖傳到的，若這樣的山頭不只一個，則輸出編號最小的那個，若此山頭的呼喊無法傳到任何其他山頭，則輸出0，
這題也用廣搜思想，剛開始的時候這道題賊卡，覺得轉了一圈又回來那用什么演算法，什么資料結構啊，隨后看了百度，然后重新寫了這篇博客，復習了一下選拔賽時候的優先佇列廣搜那道題，最后這道題用的鄰接表（這個說法當時百度聽得，當時賊迷，原來是讀進一個邊就把這個邊的兩個頂點都互相標記互為鄰邊，后來在讀進一個點的時候就把這個點的鄰點（因為不知道幾個鄰點，要不然不好訪問，所以用vector存）都若沒有visit過就進入佇列，每個node都包含num（哪個點）和dep（第幾層）每做一次就判斷是不是最深的，因為資料賊小，就懶得優化了，每次判斷最深的各個哪個最小就存哪個，最后輸出，用佇列和BFS，
代碼：
#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);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/122746.html
標籤：其他
上一篇：給那些抱怨的低能程式員
下一篇：幾種常見的排序演算法集錦