超級(jí)源點(diǎn)和匯點(diǎn)

超級(jí)源點(diǎn)跟超級(jí)匯點(diǎn)是模擬出來(lái)的虛擬點(diǎn)，多用于圖中：
<1>同時(shí)有多個(gè)匯點(diǎn)和一個(gè)源點(diǎn)，建立超級(jí)匯點(diǎn)
1、2、3、6分別到達(dá)4或者5或者7的最短路徑，設(shè)立0這個(gè)超級(jí)匯點(diǎn)。

<2>同時(shí)有多個(gè)源點(diǎn)和一個(gè)匯點(diǎn)，建立超級(jí)源點(diǎn)
<3>同時(shí)有多個(gè)源點(diǎn)和多個(gè)匯點(diǎn)，建立超級(jí)源點(diǎn)和超級(jí)匯點(diǎn)

最短距離[超級(jí)匯點(diǎn)]

題目連接：https://www.acwing.com/problem/content/1490/
思路分析：這個(gè)題的關(guān)鍵就在于模擬出來(lái)一個(gè)超級(jí)匯點(diǎn)，對(duì)于每個(gè)村莊來(lái)說(shuō)，目的地都是一個(gè)商店，具體是哪一個(gè)商店是不要求的，只需要找到最近的一個(gè)商店，也就是找到到這些商店集合的最短路徑，虛擬出來(lái)一個(gè)超級(jí)匯點(diǎn)，到這些商店的路徑都為0，這樣每個(gè)村莊到達(dá)集合的最短路徑其實(shí)就是到達(dá)這個(gè)超級(jí)匯點(diǎn)的最短路徑了，也就相當(dāng)于是這個(gè)超級(jí)匯點(diǎn)到每個(gè)點(diǎn)的最短路徑，進(jìn)行一次dijstra就行，也就簡(jiǎn)化成了求點(diǎn)到點(diǎn)的最短路徑。
AC代碼：

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int N=100005;
const int INF=0x3f3f3f3f;
typedef pair<int,int>PII;
vector<PII>adj[N];
int dist[N];
bool visited[N];
int n,m,k,q,x;
priority_queue<PII,vector<PII>,greater<PII>>que;void dijistra(int s)
{for(int i=0;i<=n;i++)  dist[i]=INF; dist[s]=0; que.push({0,s});while(!que.empty()){int min=que.top().second;que.pop();if(visited[min]) continue;visited[min]=true;for(int i=0;i<adj[min].size();i++){if(!visited[adj[min][i].first]&&dist[min]+adj[min][i].second<dist[adj[min][i].first]){dist[adj[min][i].first]=dist[min]+adj[min][i].second;que.push({dist[adj[min][i].first],adj[min][i].first});}}}
}
int main()
{cin>>n>>m;while(m--){int u,v,c; cin>>u>>v>>c;  adj[u].push_back({v,c}); adj[v].push_back({u,c});}cin>>k;while(k--){cin>>x;   adj[0].push_back({x,0}); adj[x].push_back({0,0});}dijistra(0); cin>>q; while(q--){cin>>x; cout<<dist[x]<<endl;}return 0;
}

昂貴的聘禮

刷題鏈接：https://www.acwing.com/problem/content/905/
思路分析：到底怎么建立圖是很關(guān)鍵的，必要的時(shí)候要加一些超級(jí)源點(diǎn)和超級(jí)匯點(diǎn)
還是注意要建立一個(gè)超級(jí)源點(diǎn)，表示最后終止繼續(xù)交換下去的那個(gè)人的花費(fèi)是他的物品的價(jià)格；
最后要保證求出來(lái)的最短路包含的結(jié)點(diǎn)的等級(jí)相互之間都不超過(guò)m，只能是枚舉這個(gè)等級(jí)區(qū)間了，不能說(shuō)每次更新鄰接結(jié)點(diǎn)的時(shí)候判斷該結(jié)點(diǎn)距離當(dāng)前納入最短路徑集合的結(jié)點(diǎn)的距離，如果超過(guò)了m就不更新，這樣只能保證相鄰的兩個(gè)結(jié)點(diǎn)的等級(jí)是不超過(guò)m的，但是最后最短路徑包含的全部結(jié)點(diǎn)相互間不一定都不超過(guò)m，規(guī)則是只要跟一個(gè)很高的人交換了，后面涉及的所有等級(jí)很低的人都不能再進(jìn)行交換
AC代碼：

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int N=105;
const int INF=0x3f3f3f3f;
typedef pair<int,int>PII;  //first表示未結(jié)點(diǎn)編號(hào)，second表示到達(dá)該結(jié)點(diǎn)的優(yōu)惠 
vector<PII>adj[N];
int dist[N];
bool visited[N];
int m,n,p,l,x,t,v;
int Rank[N];   //存儲(chǔ)每個(gè)結(jié)點(diǎn)的等級(jí) 
priority_queue<PII,vector<PII>,greater<PII>>que;int dijistra(int down,int up)  //傳入?yún)^(qū)間等級(jí)最大和最小值 
{for(int i=0;i<=n;i++){dist[i]=INF; visited[i]=false;}dist[0]=0;que.push({0,0});while(!que.empty()){int min=que.top().second;que.pop();if(visited[min]) continue;visited[min]=true;for(int i=0;i<adj[min].size();i++){//超級(jí)源點(diǎn)跟誰(shuí)都能到達(dá) if(Rank[adj[min][i].first]>up||Rank[adj[min][i].first]<down) continue;   //等級(jí)相差太大，無(wú)法到達(dá) if(!visited[adj[min][i].first]&&dist[min]+adj[min][i].second<dist[adj[min][i].first]){dist[adj[min][i].first]=dist[min]+adj[min][i].second;que.push({dist[adj[min][i].first],adj[min][i].first});}}}return dist[1];
}
int main()
{cin>>m>>n;for(int i=1;i<=n;i++){cin>>p>>l>>x;adj[0].push_back({i,p});   //建立超級(jí)源點(diǎn)到該點(diǎn)的邊權(quán)Rank[i]=l;while(x--)  //替代品們 {cin>>t>>v;adj[t].push_back({i,v});   //建立替代品到該點(diǎn)的邊權(quán)} }int ans=INF;for(int i=Rank[1]-m;i<=Rank[1];i++){ans=min(ans,dijistra(i,i+m));   //超級(jí)源點(diǎn)到每個(gè)點(diǎn)的最短路徑 }cout<<ans<<endl; return 0;
}

多源BFS

單源BFS：起始階段只需要將某一個(gè)元素加入隊(duì)列
二叉樹(shù)層序遍歷
多源BFS：開(kāi)始階段加入多個(gè)元素入隊(duì)列，可以將其理解為存在一個(gè)超級(jí)源點(diǎn)，然后進(jìn)行寬搜擴(kuò)展，第一階段會(huì)把距離為0的點(diǎn)擴(kuò)展進(jìn)隊(duì)列進(jìn)行求解最短距離，第二階段會(huì)把距離為1的點(diǎn)擴(kuò)展進(jìn)隊(duì)列進(jìn)行求解最短距離，第三階段會(huì)把距離為2的點(diǎn)擴(kuò)展進(jìn)隊(duì)列進(jìn)行求解最短距離，…最后成功將所有點(diǎn)距離目標(biāo)點(diǎn)的最短距離求出來(lái)了。

矩陣距離

題目鏈接：https://www.acwing.com/problem/content/description/175/
思路分析：曼哈頓距離實(shí)際就是從1位置處向外擴(kuò)展，每次擴(kuò)展距離加1
AC代碼：

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef pair<int,int>PII;
queue<PII>tou;
const int INF=0x3f3f3f3f;
const int N=1005;
int grid[N][N];
int off[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
int main()
{cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){char t;cin>>t;if(t=='1') {grid[i][j]=0;tou.push({i,j});}else grid[i][j]=-1;}}while(!tou.empty()){int x=tou.front().first;int y=tou.front().second;tou.pop();for(int i=0;i<4;i++){int xi=x+off[i][0],yi=y+off[i][1];if(xi>=0 && yi>=0 &&xi<n && yi<m && grid[xi][yi]<0){tou.push({xi,yi});grid[xi][yi]=grid[x][y]+1;}}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<grid[i][j]<<" ";}cout<<endl;}return 0;
}