目錄

今天知識點(diǎn)??

di和sp求到每個點(diǎn)的最短路數(shù)?

floyd求到點(diǎn)的最短路數(shù)和經(jīng)過點(diǎn)的最短路數(shù)

求三點(diǎn)最短距離

每個點(diǎn)有多個狀態(tài)，建立分層圖

求第二短路

題目：最短路計(jì)數(shù)

思路：

題目：社交網(wǎng)絡(luò)

思路：

題目：公園

思路：

題目：飛行路線?

思路：

題目：第二短路

思路：

????????

?????

題目：最短路計(jì)數(shù)

? ? ? ? ??????????

思路：

????????

注意到每條路徑的權(quán)值都是1，難怪結(jié)果會那么大。

????????

dikjkstra和spfa版本最短路計(jì)數(shù)：
?? ?if(dis[u]+1<dis[v]) ? ? ? ans[v]=ans[u],dis[v]=dis[u]+1?? ?
?? ?else if(dis[u]+1==dis[v]) ans[v]+=ans[u]

????????
1，維護(hù)最短路時產(chǎn)生的：那就是映射關(guān)系（因?yàn)橐氲氖侵車c(diǎn)，相當(dāng)于ans[v]=ans[cur]*1）
2，新最短路：發(fā)現(xiàn)了新的最短路就相加

????????
也就是說我們只需要在更新路徑的時候順序更新記錄最短路數(shù)的數(shù)組即可，相當(dāng)于將兩個dp式子一起執(zhí)行了

????????

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1e6+5,M=2e6+5;
int mod=100003,n,m,tot=0;
int head[N],vis[N],dis[N],ans[N];
priority_queue<pii,vector<pii>,greater<pii>>Q;
struct node {int to;int next;}e[M*2];
void add(int u,int v){e[++tot]=(node){v,head[u]};head[u]=tot;}
void dijkstra(int s){
	memset(dis,0x3f,sizeof(dis));
	Q.push({0,s});dis[s]=0;ans[s]=1;
	while(!Q.empty()){
		int cur=Q.top().second;Q.pop();
		if(vis[cur])continue;//跳不跳無所謂，無非耗點(diǎn)時間
		vis[cur]=1;
		for(int i=head[cur];i;i=e[i].next)
		{
			int v=e[i].to;
			if(dis[cur]+1<dis[v])dis[v]=dis[cur]+1,ans[v]=ans[cur],Q.push({dis[v],v});//映射最短路(路過此點(diǎn)可以變短，那么最短路就和它有關(guān))
			else if(dis[cur]+1==dis[v])ans[v]+=ans[cur],ans[v]%=mod;//新最短路(發(fā)現(xiàn)了另外的最短路就相加)
		}
	}
}
int main(){
	cin>>n>>m;int x,y;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dijkstra(1);
	//spfa(1);
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<'\n';
	}
}

?????????????????文章來源地址http://www.zghlxwxcb.cn/news/detail-758609.html

//spfa版本：這個版本更快！?。。?void spfa(int s){
	memset(dis,0x3f,sizeof(dis));
	queue<int>q;vis[s]=1;
	q.push(s);dis[s]=0;ans[s]=1;
	while(!q.empty()){
		int cur=q.front();q.pop();
		vis[cur]=0;
		for(int i=head[cur];i;i=e[i].next){
			int v=e[i].to;
			if(dis[cur]+1<dis[v]){
			   dis[v]=dis[cur]+1;
			   ans[v]=ans[cur];
			   if(!vis[v])q.push(v),vis[v]=1;	
			}
			else if(dis[cur]+1==dis[v])ans[v]+=ans[cur],ans[v]%=mod;
		}
	}
}

????????

????????

題目：社交網(wǎng)絡(luò)

????????????????

思路：

????????

點(diǎn)i的重要程度=∑從s到t的且經(jīng)過i最短路條數(shù)/從s到t的最短路條數(shù)（s!=i，t!=i）

主要還是floyd算法，求出每個(i,j)對每個k的重要程度為ans[k]
求到某點(diǎn)時最短路徑數(shù)：
1，只要最短路更新，那么最短路個數(shù)也要更新 e[i][j]=e[i][k]*e[k][j]
2，如果發(fā)現(xiàn)了新的最短路，那么就相加?? ?e[i][j]+=e[i][k]*e[k][j];
????????

#include <bits/stdc++.h>
using namespace std;   
typedef long long ll;
const int N=110;
ll INF,dis[N][N],e[N][N];//e[i][j]表示（i，j）的最短路徑數(shù)
double ans[N];//每個點(diǎn)的重要程度
int main(){
	int n,m;ll x,y,z;
	cin>>n>>m;
	memset(dis,0x7f,sizeof(dis));
	INF=dis[1][1];//初始化INF無窮大
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&x,&y,&z);
		dis[x][y]=dis[y][x]=z;
		e[x][y]=e[y][x]=1;//初始化e[i][j]
	}
	for(int i=1;i<=n;i++)  dis[i][i]=0;//對角線為0，但是不寫也對其余任何邊都沒有影響，寫不寫隨你
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(dis[i][k]==INF||dis[k][j]==INF)continue;//有不通的就直接跳過
			if(dis[i][j]>dis[i][k]+dis[k][j]){
				dis[i][j]=dis[i][k]+dis[k][j];//每個邊只會更新一次，即當(dāng)前最優(yōu)
				e[i][j]=e[i][k]*e[k][j];//只要最短路更新，則最短路對應(yīng)的個數(shù)也要更新即可
				continue;
			}
			if(dis[i][j]==dis[i][k]+dis[k][j]){//找到了第二條最短路，就相加
				e[i][j]+=e[i][k]*e[k][j];
			}
		}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(i==j||j==k||i==k)continue;
			if(dis[i][j]==dis[i][k]+dis[k][j])//對k遍歷每個（i，j）
				ans[k]+=(1.0*e[i][k]*e[k][j])/e[i][j];
		}
	for(int i=1;i<=n;i++)
		printf("%0.3f\n",ans[i]);
}

? ? ? ?

題目：公園

今天是六一節(jié)，小度去公園玩，公園一共?N?個景點(diǎn)，正巧看到朋友圈度度熊也在這個公園玩，于是他們約定好一塊去景點(diǎn)?N。 小度當(dāng)前所在景點(diǎn)編號為?T，從一個景點(diǎn)到附近的景點(diǎn)需要消耗的體力是?TE，而度度熊所在景點(diǎn)編號為?F?，移動消耗為?FE。 好朋友在一塊，趕路都會開心很多，所以如果小度和度度熊一塊移動(即在相同位置向相同方向移動)，每一步他倆的總消耗將會減少?S。
求他倆到景點(diǎn)?N?時，所需要的總消耗最少是多少？

?????????

輸入：

4 4 3
1 2 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8

輸出：

22

思路：

其實(shí)注意到兩個人的消耗是固定的，既然不知道在哪相遇，不妨把每個點(diǎn)都做中間相遇點(diǎn)試試，(你看看，出題人就是想讓你暴力的)。

我們先對3個點(diǎn)找各自到其他點(diǎn)的最短距離，假如a點(diǎn)是相遇點(diǎn)，那么三個點(diǎn)(小度，小熊，終點(diǎn))到此點(diǎn)a的最短距離×各自三個消耗(消耗怎么算？就看走了多長就行，因?yàn)槊慷痰南氖且粯拥?，這樣的話，一種答案就出來了，然后找出最優(yōu)答案即可。

其實(shí)，從這道題，你發(fā)現(xiàn)了什么？是不是找3個點(diǎn)的最近距離問題！
????????

#include <bits/stdc++.h>    
using namespace std;   //暴力枚舉
typedef pair<int,int> pa;
const int N=40005;
int dis[3][N],head[N];
int s1,s2,n,m;  
long long ans=1e17;
priority_queue<pa,vector<pa>,greater<pa>> Q;
struct node{int to;int next;}e[N*2]; //就是喜歡用鏈?zhǔn)角靶?void add(int u,int v){
	static int i=0;i++;
	e[i].to=v;
	e[i].next=head[u];head[u]=i;
}
void dijkstra(int s,int dis[]){ //int dis[]=a[length],這樣傳參挺好的
	for(int i=0;i<=n;i++)dis[i]=40000;
	dis[s]=0;
	Q.push(make_pair(0,s));
	while(!Q.empty()){
		int u=Q.top().second;int dis_=Q.top().first;Q.pop();
		if(dis_!=dis[u]) continue;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			if(dis[v]>dis[u]+1)
				dis[v]=dis[u]+1,Q.push(make_pair(dis[v],v));
		}
	}	
}
int main(){
	long long e1,e2,e3; //之所以ll型，是因?yàn)閐is是int型，運(yùn)算時方便給ll型ans賦值（類型隱式轉(zhuǎn)換）
	cin>>e1>>e2>>e3;  //e1，e2是兩人的消耗，e3是減少的消耗：
	cin>>s1>>s2>>n>>m;//s1，s2是兩個人的起點(diǎn)，n，m是景點(diǎn)數(shù)和邊數(shù)
	int u,v;
	while(m--){
		scanf("%d %d",&u,&v);
		add(u,v);add(v,u);  //建邊
	}
	dijkstra(s1,dis[0]); //尋找3個點(diǎn)到其余點(diǎn)的最短距離
	dijkstra(s2,dis[1]);
	dijkstra(n,dis[2]);
	for(int i=1;i<=n;i++){ //如果dis沒有變說明這個點(diǎn)到不了，標(biāo)記一下
		if(dis[0][i]==40000)dis[0][i]=-1;
		if(dis[1][i]==40000)dis[1][i]=-1;
		if(dis[2][i]==40000)dis[2][i]=-1;
	}
	for(int i=1;i<=n;i++){ 
		if(dis[0][i]!=-1&&dis[1][i]!=-1&&dis[2][i]!=-1) //3個點(diǎn)都要能到才算有效（能連起來）
		ans=min(ans,dis[0][i]*e1+dis[1][i]*e2+dis[2][i]*(e1+e2-e3)); //（ll*int）->ll類型
	}
	if(ans==1e17){cout<<-1;return 0;}//3個點(diǎn)沒有一個公共交點(diǎn)，即3個點(diǎn)連不起來
	cout<<ans;
	return 0;
}

????????

????????

題目：飛行路線?

????????

?????????????????????????

思路：

????????

?一個圖中任意兩個點(diǎn)都可以權(quán)值變成0，最多有k次，我們常常建立k層的分層圖，相鄰層所有點(diǎn)建立權(quán)值為0的立體邊，然后跑最短路即可
????????

#include <bits/stdc++.h> 
using namespace std;
int cnt,head[110005];
int dis[110005];
bool vis[110005]; //標(biāo)記當(dāng)前白點(diǎn)，如果不想用vis，也可以判斷取出元素的dis和dis數(shù)組中值是否一樣
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > Q; //堆優(yōu)化(first是值，second是下標(biāo))
struct Edge{ int to,w,next;}e[2500001];
void add(int u,int v,int w) { e[++cnt]=(Edge){v,w,head[u]}; head[u]=cnt;}
void Dijkstra(int s)//dijktra+堆優(yōu)化
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    Q.push(make_pair(0,s));
    while(!Q.empty())  //必須用empty， size是求大小的，會慢一些 !!!
    {
		int u=Q.top().second; Q.pop();
		if(vis[u]) continue; //已經(jīng)是白點(diǎn)的就跳過
	    vis[u]=1; //標(biāo)記成白點(diǎn)
	    for(int i=head[u];i;i=e[i].next)
	    {
	        int v=e[i].to,w=e[i].w;
	        if(dis[v]>dis[u]+w) dis[v]=dis[u]+w,Q.push(make_pair(dis[v],v));
	    }
    }    
}

int main()
{
	int n,m,k,s,t;
	cin>>n>>m>>k>>s>>t; //城市數(shù)，航線數(shù)，免費(fèi)次數(shù)，起始城市號，終點(diǎn)城市號
    int u,v,c;
    for(int i=0;i<m;++i)
    {
    	cin>>u>>v>>c;//兩個城市航線，費(fèi)用
    	for(int j=0;j<=k;++j){//建立每層圖
    		add(u+j*n,v+j*n,c);
            add(v+j*n,u+j*n,c);
            if(j!=k){//第k層下面沒有了，就別建了
            	add(u+j*n,v+(j+1)*n,0); //分層圖：所有相鄰層間：上下層u，v的權(quán)值為0
            	add(v+j*n,u+(j+1)*n,0);
			}
		}
    }
    for(int i=1;i<=k;++i)
	{
		add(t+(i-1)*n,t+i*n,0);
	}//處理奇葩數(shù)據(jù)
    Dijkstra(s);
    printf("%d",dis[t+k*n]);
    return 0;
}

?????????

?????????

題目：第二短路

?????????????????

思路：

#include<bits/stdc++.h>
using namespace std;   
typedef pair<int,int> pii;
const int N=5005,M=100005;
int n,m,tot,flag;
int head[N],d1[N],d2[N],vis[N];
priority_queue<pii,vector<pii>,greater<pii> > Q;
struct node{int to;int w;int next;}e[M*2];
void add(int u,int v,int w){e[++tot]=(node){v,w,head[u]};head[u]=tot;}
void dijkstra(int s){
	memset(d1,0x3f,sizeof(d1));//d1存放第一短路
	memset(d2,0x3f,sizeof(d2));//d2存放第二短路
	Q.push(make_pair(0,s));d1[s]=0;
	while(!Q.empty()){
		int cur=Q.top().second;Q.pop();
		if(vis[cur])continue;//vis數(shù)組可有可無，即便舊白點(diǎn)引入也掀不起變化，無非多走了幾步
		vis[cur]=1;
		for(int i=head[cur];i;i=e[i].next){
			int v=e[i].to,w=e[i].w;flag=0;
			if(d1[cur]+w<d1[v])d2[v]=d1[v],d1[v]=d1[cur]+w,flag=1;//維護(hù)最短路，更新前的最短路就是次短路
			if(d1[cur]+w>d1[v]&&d1[cur]+w<d2[v])d2[v]=d1[cur]+w,flag=1;//最短路沒有變化，更新次短路
			if(d2[cur]+w<d2[v])d2[v]=d2[cur]+w,flag=1;//維護(hù)次短路,如果d2[s]初始化成0,那么這個地方就出問題了
			if(flag)Q.push(make_pair(d1[v],v));
		}
	}
}
int main(){
	cin>>n>>m;int u,v,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);add(v,u,w);
	}
	dijkstra(1);
	cout<<d2[n];
}

到了這里，關(guān)于【算法每日一練]-圖論（保姆級教程 篇4（最短路，分層圖） #最短路計(jì)數(shù) #社交網(wǎng)絡(luò) #公園 #飛行路線 # 第二短路的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！