超級源點和匯點

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

<2>同時有多個源點和一個匯點，建立超級源點
<3>同時有多個源點和多個匯點，建立超級源點和超級匯點

最短距離[超級匯點]

題目連接：https://www.acwing.com/problem/content/1490/
思路分析：這個題的關(guān)鍵就在于模擬出來一個超級匯點，對于每個村莊來說，目的地都是一個商店，具體是哪一個商店是不要求的，只需要找到最近的一個商店，也就是找到到這些商店集合的最短路徑，虛擬出來一個超級匯點，到這些商店的路徑都為0，這樣每個村莊到達(dá)集合的最短路徑其實就是到達(dá)這個超級匯點的最短路徑了，也就相當(dāng)于是這個超級匯點到每個點的最短路徑，進(jìn)行一次dijstra就行，也就簡化成了求點到點的最短路徑。
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)鍵的，必要的時候要加一些超級源點和超級匯點
還是注意要建立一個超級源點，表示最后終止繼續(xù)交換下去的那個人的花費是他的物品的價格；
最后要保證求出來的最短路包含的結(jié)點的等級相互之間都不超過m，只能是枚舉這個等級區(qū)間了，不能說每次更新鄰接結(jié)點的時候判斷該結(jié)點距離當(dāng)前納入最短路徑集合的結(jié)點的距離，如果超過了m就不更新，這樣只能保證相鄰的兩個結(jié)點的等級是不超過m的，但是最后最短路徑包含的全部結(jié)點相互間不一定都不超過m，規(guī)則是只要跟一個很高的人交換了，后面涉及的所有等級很低的人都不能再進(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é)點編號，second表示到達(dá)該結(jié)點的優(yōu)惠 
vector<PII>adj[N];
int dist[N];
bool visited[N];
int m,n,p,l,x,t,v;
int Rank[N];   //存儲每個結(jié)點的等級 
priority_queue<PII,vector<PII>,greater<PII>>que;int dijistra(int down,int up)  //傳入?yún)^(qū)間等級最大和最小值 
{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++){//超級源點跟誰都能到達(dá) if(Rank[adj[min][i].first]>up||Rank[adj[min][i].first]<down) continue;   //等級相差太大，無法到達(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});   //建立超級源點到該點的邊權(quán)Rank[i]=l;while(x--)  //替代品們 {cin>>t>>v;adj[t].push_back({i,v});   //建立替代品到該點的邊權(quán)} }int ans=INF;for(int i=Rank[1]-m;i<=Rank[1];i++){ans=min(ans,dijistra(i,i+m));   //超級源點到每個點的最短路徑 }cout<<ans<<endl; return 0;
}

多源BFS

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

矩陣距離

題目鏈接：https://www.acwing.com/problem/content/description/175/
思路分析：曼哈頓距離實際就是從1位置處向外擴展，每次擴展距離加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;
}