图论(2)：最短路

最短路

  • 一、模板
    • 1. Floyd
    • 2. 01BFS
    • 3. SPFA
    • 4. Dijkstra（弱化版）
    • 5. Dijkstra（优化版）
  • 二、例题
    • 1. Floyd
      • 1.1 传送门
      • 1.2 无向图最小环
      • 1.3 灾后重建
      • 1.4 飞猪
    • 2. 01BFS
      • 2.1 Kathiresan
      • 2.2 障碍路线
      • 2.3 奇妙的棋盘
    • 3. SPFA
      • 3.1 奶牛派对
      • 3.2 营救
      • 3.3 航空路线
      • 3.4 牛奶管道
    • 4. Dijkstra
      • 4.1 路径统计
      • 4.2 平面上的点
      • 4.3 邀请函

一、模板

1. Floyd

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e2+8;
const int INF=0x3f3f3f3f;
int n,m,dis[MAXN][MAXN];
int main(){cin>>n>>m;memset(dis,INF,sizeof(dis));for(int u=1;u<=n;u++)dis[u][u]=0;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,dis[u][v]=min(dis[u][v],w);for(int k=1;k<=n;k++)for(int u=1;u<=n;u++)for(int v=1;v<=n;v++)dis[u][v]=min(dis[u][v],dis[u][k]+dis[k][v]);for(int u=1;u<=n;u++)for(int v=1;v<=n;v++)cout<<(dis[u][v]==INF?-1:dis[u][v])<<" \n"[v==n];return 0;
}

2. 01BFS

原题：求 KKK 的所有非 000 倍数中十进制表示下数码和的最小值

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int INF=0x3f3f3f3f;
int k,dis[MAXN];//除以k余数为x的数中最小的数码和
int bfs(){deque<int>dque;dis[1]=1,dque.push_back(1);while(!dque.empty()){int x=dque.front(),nx;dque.pop_front();if(x==0)return dis[x];//代价为0的操作，放在队首nx=x*10%k;//x后面直接加0，十进制数码和不变，放在队首if(dis[nx]>dis[x])dis[nx]=dis[x],dque.push_front(nx);//代价为1的操作，放在队尾nx=(x+1)%k;//x+1和x的数码和差1，放在队尾if(dis[nx]>dis[x]+1)dis[nx]=dis[x]+1,dque.push_back(nx);}
}
int main(){cin>>k;memset(dis,INF,sizeof(dis));cout<<bfs();return 0;
}

3. SPFA

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
int n,m,s,dis[MAXN];
bool in_que[MAXN];
vector<Edge>adj[MAXN];
void spfa(int s){queue<int>que;dis[s]=0,in_que[s]=true,que.push(s);while(!que.empty()){int u=que.front();in_que[u]=false,que.pop();for(auto[v,w]:adj[u])if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;if(!in_que[v])in_que[v]=true,que.push(v);}}
}
int main(){cin>>n>>m>>s;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[u].push_back({v,w});memset(dis,INF,sizeof(dis));spfa(s);for(int i=1;i<=n;i++)cout<<(dis[i]==INF?INT32_MAX:dis[i])<<" ";return 0;
}

4. Dijkstra（弱化版）

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
bool vis[MAXN];
int n,m,s,t,dis[MAXN];
vector<Edge>adj[MAXN];
void dijkstra(int s){dis[s]=0;for(int i=1;i<=n;i++){int u=0;for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]<dis[u])u=j;if(!u)return;vis[u]=true;for(auto[v,w]:adj[u])if(!vis[v]&&dis[v]>dis[u]+w)dis[v]=dis[u]+w;}
}
int main(){cin>>n>>m>>s>>t;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[u].push_back({v,w}),adj[v].push_back({u,w});memset(dis,INF,sizeof(dis));dijkstra(s);cout<<dis[t];return 0;
}

5. Dijkstra（优化版）

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
bool vis[MAXN];
int n,m,s,t,dis[MAXN];
vector<Edge>adj[MAXN];
void dijkstra(int s){//两种方法均可，推荐没有注释的代码priority_queue<pair<int,int> >pq;//{-dis[u],u}dis[s]=0,pq.push({0,s});while(!pq.empty()){auto u=pq.top().second;pq.pop();if(vis[u])continue;vis[u]=true;for(auto[v,w]:adj[u])if(dis[v]>dis[u]+w)dis[v]=dis[u]+w,pq.push({-dis[v],v});}// priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;// dis[s]=0,pq.push({0,s});// while(!pq.empty()){//     auto[d,u]=pq.top();//     pq.pop();//     if(d>dis[u])continue;//     for(auto[v,w]:adj[u])//         if(dis[v]>dis[u]+w) {//             dis[v]=dis[u]+w;//             pq.push({dis[v],v});//         }// }
}
int main(){cin>>n>>m>>s;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[u].push_back({v,w});memset(dis,INF,sizeof(dis));dijkstra(s);for(int i=1;i<=n;i++)cout<<(dis[i]==INF?INT32_MAX:dis[i])<<" ";return 0;
}

二、例题

1. Floyd

1.1 传送门

香蕉大学里有 nnn 栋教学楼，有 mmm 条双向通行道路连接这些教学楼，不存在重边和自环。每条道路都有一定的长度，而且所有教学楼之间都可以直接或者间接的通过道路到达。我们可以很容易的求出这些教学楼之间的最短路。
为了使交通更为顺畅，校方决定在两个教学楼里增设一对传送门。传送门可以将这对教学楼的距离直接缩短为 000。利用传送门，某些教学楼之间的最短路的距离就变短了。
由于预算有限，学校里只能安装一对传送门。但是校长希望尽可能方便学生，使任意两点之间的最短路长度的总和最小。当然啦，从 xxx 教学楼到 yyy 教学楼的长度和从 yyy 教学楼到 xxx 教学楼的长度只需要统计一次就可以了。

标准的一道暴力枚举题。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e2+8;
const int INF=0x3f3f3f3f;
int n,m,dis[MAXN][MAXN];
int main(){cin>>n>>m;memset(dis,INF,sizeof(dis));for(int u=1;u<=n;u++)dis[u][u]=0;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,dis[u][v]=dis[v][u]=min(dis[u][v],w);for(int k=1;k<=n;k++)for(int u=1;u<=n;u++)for(int v=1;v<=n;v++)dis[u][v]=min(dis[u][v],dis[u][k]+dis[k][v]);int ans=INF;for(int i=1;i<=n;i++)//枚举传送门端点Afor(int j=i+1;j<=n;j++){//枚举传送门端点Bint sum=0;//存储安装传送门后所有点对的最短路总和for(int u=1;u<=n;u++)//枚举所有起点计算最短路总和for(int v=u+1;v<=n;v++)//枚举所有终点计算最短路总和   sum+=min({//因为i和j间有传送门，视其距离为0dis[u][v],dis[u][i]+dis[j][v],dis[u][j]+dis[i][v]});ans=min(ans,sum);//每次更新答案到最小值}cout<<ans;return 0;
}

1.2 无向图最小环

给定一个 nnn 个点 mmm 条带正权边且无重边的无向图，请输出图中简单环的最小权值和。特别地，如果图中没有简单环则输出 "No Simple Cycle"。本题中的简单环是指，不重复经过同一个点，且不重复经过同一条边的环。

比较经典的一道松弛类型的题目。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e2+8;
const int INF=0x3f3f3f3f;
int t,dis[MAXN][MAXN],tmp[MAXN][MAXN];
int main(){cin>>t;while(t--){int n,m;cin>>n>>m;memset(dis,INF,sizeof(dis));memset(tmp,INF,sizeof(tmp));for(int u=1;u<=n;u++)dis[u][u]=tmp[u][u]=0;for(int j=1,u,v,w;j<=m;j++){cin>>u>>v>>w;dis[u][v]=dis[v][u]=min(dis[u][v],w);tmp[u][v]=tmp[v][u]=min(tmp[u][v],w);}int ans=INF;//最小环的权值和for(int k=1;k<=n;k++){//寻找所有i<k和j<k的通过k的形如i-j-k-i的环for(int i=1;i<k;i++)for(int j=i+1;j<k;j++)if(dis[i][j]!=INF&&tmp[j][k]!=INF&&tmp[k][i]!=INF)ans=min(ans,dis[i][j]+tmp[j][k]+tmp[k][i]);//使用tmp而非dis，防止重复顶点的出现for(int i=1;i<=n;i++)//用Floyd松弛for(int j=1;j<=n;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);}if(ans==INF)cout<<"No Simple Cycle\n";else cout<<ans<<"\n";}return 0;
}

1.3 灾后重建

题目传送门

由于题目保证每次输入都是不下降的，考虑寻找已经重建好的村庄 kkk 作为中转站，以寻找两村庄之间的最短路进行更新和输出。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e2+8;
const int INF=0x3f3f3f3f;
int n,m,q,tms[MAXN],dis[MAXN][MAXN];
int main(){cin>>n>>m;memset(dis,INF,sizeof(dis));for(int u=0;u<n;u++)dis[u][u]=0;for(int i=0;i<n;i++)cin>>tms[i];for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,dis[u][v]=dis[v][u]=min(dis[u][v],w);cin>>q;for(int i=1,x,y,t,k=0;i<=q;i++){cin>>x>>y>>t;while(k<n&&tms[k]<=t){for(int u=0;u<n;u++)for(int v=0;v<n;v++)dis[u][v]=min(dis[u][v],dis[u][k]+dis[k][v]);k++;}if(tms[x]<=t&&tms[y]<=t&&dis[x][y]<INF)cout<<dis[x][y]<<"\n";else cout<<"-1\n";}return 0;
}

1.4 飞猪

给定一个 nnn 个点 mmm 条边的边带权简单连通无向图，在 000 时刻你在点 111 上。
假设当前是 ttt 时刻，你在点 vvv 上，你可以选择两种操作：

  • 仍停留在点 vvv 上，操作后到 t+1t+1t+1 时刻。
  • 选择一条边 (a,b,w)(a,b,w)(a,b,w) 满足 a=va=va=v 或 b=vb=vb=v，则你到这条边连接的另一个点上，操作后到 t+wt+wt+w 时刻。

有 kkk 条信息，每一条信息形如 (ti,vi)(t_i,v_i)(ti​,vi​) 表示在 tit_iti​ 时刻，点 viv_ivi​ 上会出现一只飞猪，其编号为 iii，若该时刻你在 viv_ivi​ 上，则你捕获到了 iii 号飞猪。
现在你需要求出你能捕获到的飞猪数量的最大值。

看到中间分的两种情况可以立刻想到动态规划的做法，再结合要从 aaa 到达 bbb 想到最短路。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e2+8;
const int MAXK=5e3+8;
const int INF=0x3f3f3f3f;
int n,m,k,dis[MAXN][MAXN],dp[MAXK];//dp[i]表示捕获第i只飞猪时的最大飞猪数量
struct Pig{int t,idx;bool operator<(const Pig&rhs)const{return t<rhs.t;}
}pigs[MAXK];
int main(){cin>>n>>m>>k;memset(dis,INF,sizeof(dis));for(int u=1;u<=n;u++)dis[u][u]=0;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,dis[u][v]=dis[v][u]=min(dis[u][v],w);for(int k=1;k<=n;k++)//Floydfor(int u=1;u<=n;u++)for(int v=1;v<=n;v++)dis[u][v]=min(dis[u][v],dis[u][k]+dis[k][v]);for(int i=1;i<=k;i++)cin>>pigs[i].t>>pigs[i].idx;sort(pigs+1,pigs+k+1);memset(dp,-INF,sizeof(dp));pigs[0].idx=1,dp[0]=0;//0时刻在节点1（初始位置）捕获0只飞猪for(int i=1;i<=k;i++)//遍历每只飞猪ifor(int j=0;j<i;j++)//尝试从之前的飞猪j转移过来if(pigs[j].t+dis[pigs[j].idx][pigs[i].idx]<=pigs[i].t)//从j的时间和位置，能否在i出现前到达i的位置dp[i]=max(dp[i],dp[j]+1);//若可达，则更新dp[i]为捕获j后再捕获i的数量int ans=0;for(int i=1;i<=k;i++)ans=max(ans,dp[i]);cout<<ans;return 0;
}

2. 01BFS

2.1 Kathiresan

Kathiresan 被关在一个高度戒备的矩形监狱中的单元格 (0,0)(0, 0)(0,0)。他必须到达 (R−1,C−1)(R−1, C−1)(R−1,C−1) 处的大门才能逃出监狱。Kathiresan 可以从任何单元格移动到其四个相邻单元格之一，如果 Kathiresan 当前位于 (x1,y1)(x_1,y_1)(x1​,y1​)，那么他可以移动到 (x2,y2)(x_2,y_2)(x2​,y2​) 当且仅当它们的曼哈距离为 111 且 0≤x2<R0≤x_2<R0≤x2​<R 且 0≤y2<C0≤y2<C0≤y2<C。Kathiresan 设法获得了监狱的地图。如果 mapx1,y1=mapx2,y2\text{map}_{x_1,y_1}=\text{map}_{x_2,y_2}mapx1​,y1​​=mapx2​,y2​​，则 Kathiresan 可以从 (x1,y1)(x_1,y_1)(x1​,y1​) 移动到 (x2,y2)(x_2,y_2)(x2​,y2​) 而不打晕任何守卫。如果 mapx1,y1≠mapx2,y2\text{map}_{x_1,y_1} \ne \text{map}_{x_2,y_2}mapx1​,y1​​=mapx2​,y2​​，则 Kathiresan 可以通过打晕一名守卫从 (x1,y1)(x_1,y_1)(x1​,y1​) 移动到 (x2,y2)(x_2,y_2)(x2​,y2​)。给定监狱的地图，找出为了逃出监狱，Kathiresan必须打晕的最少守卫数量。

显然，代价为 000 的操作是直接移动，代价为 111 的操作是打倒一名守卫然后移动。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+8;
const int INF=0x3f3f3f3f;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int t,n,m,dis[MAXN][MAXN],grid[MAXN][MAXN];//dis:到每个单元格的最小代价
int bfs(int sx,int sy){deque<pair<int,int> >dque;dis[sx][sy]=0,dque.push_back({sx,sy});while(!dque.empty()){auto[x,y]=dque.front();dque.pop_front();if(x==n&&y==m)return dis[n][m];for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i],w=grid[nx][ny]!=grid[x][y];if(grid[nx][ny]==-1||dis[nx][ny]<=dis[x][y]+w)continue;//如果超出地图或者该格有当前最优解dis[nx][ny]=dis[x][y]+w;//保证队列始终按距离排序，先处理距离近的单元格w?dque.push_back({nx,ny}):dque.push_front({nx,ny});}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>t;while(t--){memset(dis,INF,sizeof(dis));memset(grid,-1,sizeof(grid));cin>>n>>m;char ch;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>ch,grid[i][j]=ch;cout<<bfs(1,1)<<"\n";}return 0;
}

2.2 障碍路线

考虑一个 N×NN \times NN×N（1≤N≤1001 \le N \le 1001≤N≤100）的由一个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的，它们被标记为了 'x'。例如下图：

. . B x .
. x x A .
. . . x .
. x . . .
. . x . .

贝茜发现自己恰好在点 AAA 处，她想去 BBB 处的舔盐块。但是奶牛是一种缓慢而且笨拙的动物，十分讨厌转弯。尽管如此，必要的时候她们还是会转弯的。对于一个给定的牧场，请你计算从 AAA 到 BBB 最少的转弯次数。开始的时候，贝茜可以面对任意一个方向，并且贝茜知道她一定可以到达 BBB 处。

遇到转弯类题目一定要把 dis 数组多开一个方向维度。可以发现，代价为 000 的操作是不转弯，代价为 111 的操作是转弯。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e2+8;
const int INF=0x3f3f3f3f;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
int n,sx,sy,ex,ey,grid[MAXN][MAXN],dis[MAXN][MAXN][5];
int bfs(int sx,int sy){deque<tuple<int,int,int> >dque;for(int i=0;i<4;i++)dis[sx][sy][i]=0,dque.push_back({sx,sy,i});while(!dque.empty()){auto[x,y,dir]=dque.front();dque.pop_front();if(x==ex&&y==ey)return dis[x][y][dir];for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i],w=i!=dir;if(grid[nx][ny]<0||dis[nx][ny][i]<=dis[x][y][dir]+w)continue;dis[nx][ny][i]=dis[x][y][dir]+w;w?dque.push_back({nx,ny,i}):dque.push_front({nx,ny,i});}}
}
int main(){memset(dis,INF,sizeof(dis));memset(grid,-1,sizeof(grid));cin>>n;char ch;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>ch;if(ch=='.')grid[i][j]=0;if(ch=='A')sx=i,sy=j,grid[i][j]=0;if(ch=='B')ex=i,ey=j,grid[i][j]=0;}cout<<bfs(sx,sy);return 0;
}

2.3 奇妙的棋盘

小猴在玩一个神奇的游戏，游戏中给出了一个 n×mn\times mn×m 的棋盘，棋盘中的格子有的黑，有的白。我们每次可以选择任意一个格子进行操作，然后这个格子和所有与它颜色相同的相邻的同色连通块中的所有格子的颜色全部取反。小猴想知道至少需要多少次操作可以使所有格子变成白色。

代价为 000 的操作显然是相邻格子颜色相同，而代价为 111 则是相邻格子颜色不同。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e2+8;
const int INF=0x3f3f3f3f;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int n,m,col[MAXN][MAXN],dis[MAXN][MAXN];
//col:存储格子颜色 1黑0白
//dis:到达(x,y)所需的最少操作次数
int bfs(int sx,int sy){deque<pair<int,int> >dque;dis[sx][sy]=0,dque.push_back({sx,sy});int ret=0;//记录最终需要的最少操作次数while(!dque.empty()){auto[x,y]=dque.front();dque.pop_front();//更新处理到该位置时累计需要的操作次数ret=max(ret,dis[x][y]+col[x][y]);//(x,y)是黑色说明要翻转一次，否则不用翻转for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i],w=col[nx][ny]!=col[x][y];if(col[x][y]<0||dis[nx][ny]<=dis[x][y]+w)continue;dis[nx][ny]=dis[x][y]+w;//更新到达新位置的操作次数w?dque.push_back({nx,ny}):dque.push_front({nx,ny});}}return ret;
}
int main(){cin>>n>>m;memset(col,-1,sizeof(col));char ch;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>ch,col[i][j]=ch=='B';int ans=INF;for(int x=1;x<=n;x++)for(int y=1;y<=m;y++)if(col[x][y]!=col[x-1][y]&&col[x][y]!=col[x][y-1])memset(dis,INF,sizeof(dis)),ans=min(ans,bfs(x,y));cout<<ans;return 0;
}

3. SPFA

3.1 奶牛派对

寒假到了，nnn 头牛都要去参加一场在编号为 xxx 的牛的农场举行的派对，农场之间有 mmm 条有向路，每条路都有一定的长度。每头牛参加完派对后都必须回家，无论是去参加派对还是回家，每头牛都会选择最短路径，求这 nnn 头牛的最短路径（一个来回）中最长的一条路径长度。

按照朴素写法，我们可以先计算出 n−1n-1n−1 个结点到 xxx 的最短距离，然后再计算出 xxx 到 n−1n-1n−1 个结点的最短距离。时间复杂度 O(nkm+km)O(nkm+km)O(nkm+km)，显然会超时。

考虑反向图优化。由于一个结点 aaa 到 bbb 的反向图搜索最短路就相当于 bbb 到 aaa 的正向图搜索最短路。这样在主函数中，可以只搜索两次，都以派对作为起点进行搜索。时间复杂度 O(2km)O(2km)O(2km)，不会超时。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
bool in_que[MAXN];
vector<Edge>adj[2][MAXN];
int n,m,x,dis[MAXN],ans[MAXN];
void spfa(int s,int rev){queue<int>que;dis[s]=0,in_que[s]=true,que.push(s);while(!que.empty()){int u=que.front();in_que[u]=false,que.pop();for(auto[v,w]:adj[rev][u])if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;if(!in_que[v])in_que[v]=true,que.push(v);}}
}
int main(){cin>>n>>m>>x;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[0][u].push_back({v,w}),adj[1][v].push_back({u,w});memset(dis,INF,sizeof(dis));spfa(x,0);//第一次计算所有奶牛从派对回家的最短路for(int i=1;i<=n;i++)ans[i]=dis[i];memset(dis,INF,sizeof(dis));spfa(x,1);//第二次计算所有奶牛从家去派对的最短路int mx=0;for(int i=1;i<=n;i++)ans[i]+=dis[i],mx=max(mx,ans[i]);cout<<mx;return 0;
}

3.2 营救

妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 ttt 区，而自己在 sss 区。该市有 mmm 条大道连接 nnn 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 sss 至 ttt 的路线，使得经过道路的拥挤度最大值最小。

SPFA 的变种，贼水。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
int n,m,s,t,dis[MAXN];
bool in_que[MAXN];
vector<Edge>adj[MAXN];
void spfa(int s){queue<int>que;dis[s]=0,in_que[s]=true,que.push(s);while(!que.empty()){int u=que.front();in_que[u]=false,que.pop();for(auto[v,w]:adj[u])if(dis[v]>max(dis[u],w)){dis[v]=max(dis[u],w);if(!in_que[v])in_que[v]=true,que.push(v);}}
}
int main(){cin>>n>>m>>s>>t;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[u].push_back({v,w}),adj[v].push_back({u,w});memset(dis,INF,sizeof(dis));spfa(s);cout<<dis[t];return 0;
}

3.3 航空路线

Bessie 对她农场那寒冷的天气感到厌烦，于是她准备坐飞机到一个更温暖的地方度假。不幸的是，她发现只有一个航空公司：Air Bovinia，愿意卖票给牛……并且这些票的结构有些复杂。Air Bovinia 拥有 NNN（1≤N≤10001≤N≤10001≤N≤1000）条航线，每条航线都经过两个及以上的城市。举个例子：某航线的一次航班可以从城市 111 出发，然后飞往城市 555，再飞到城市 222，最后飞到城市 888。任何城市都不会在同一条航线上出现多次。如果 Bessie 选择了一条航线，那么她可以从航线上的任意一个城市上飞机，然后在途中任意一个城市下飞机。她不必从航线的起点上飞机，再从航线的终点下飞机。每条航线都有一个确定的花费，只要它搭乘了这个航班，她就必须支付这个航班的全额花费，不论她途经了几个城市。如果 Bessie 多次搭乘了某个航班，那么每次搭乘 Bessie 都必须支付航班的花费。Bessie 想要找到从她农场所在的城市（城市 AAA）到她目的地所在城市（城市 BBB）最便宜的路线。请你告诉她最少要花多少钱，并告诉她在此基础上她最少经过多少个城市（坐飞机经过也算）。

抓住最后要求的重点：（1）要花多少钱；（2）要最少经过多少个城市。显然这是多关键字排序的经典题目。多关键字排序，即先比较第一关键字（钱数），若第一关键字相同，则比较第二关键字（城市数）。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+8;
const int MAXL=1e2+8;
const long long INF=0x3f3f3f3f3f3f3f3f;
struct Edge{int v;long long w1,w2;//w1:花费 w2:经过城市个数
};
bool in_que[MAXN];
long long dis[MAXN];
vector<Edge>adj[MAXN];
int n,s,t,cty[MAXL],sum[MAXN];
/*** cty[]: 每次航班的花费* dis[]: 起点到每个城市的最小花费* sum[]: 起点到每个城市的最少经过城市数量
**/
void spfa(int s){queue<int>que;dis[s]=0,sum[s]=0,in_que[s]=true,que.push(s);while(!que.empty()){int u=que.front();in_que[u]=false,que.pop();for(auto[v,w1,w2]:adj[u])if(dis[v]>dis[u]+w1||(dis[v]==dis[u]+w1&&sum[v]>sum[u]+w2)){//按照关键字优先级更新dis[v]=dis[u]+w1,sum[v]=sum[u]+w2;if(!in_que[v])in_que[v]=true,que.push(v);}}
}
int main(){cin>>s>>t>>n;for(int i=1,c,m;i<=n;i++){cin>>c>>m;for(int j=1;j<=m;j++){cin>>cty[j];for(int k=1;k<j;k++)adj[cty[k]].push_back({cty[j],c,j-k});}}memset(dis,INF,sizeof(dis));spfa(s);if(dis[t]>=INF)cout<<"-1 -1";else cout<<dis[t]<<" "<<sum[t];return 0;
}

3.4 牛奶管道

农民约翰的农场有一套老旧的管网，管网由 MMM 条管道（1≤M≤5001≤M≤5001≤M≤500）构成，用于将牛奶从谷仓运到储奶罐。他想在明年移除和更新大部分管道，但他想原封不动地保留一条完整的路径，这样他仍然可以把牛奶从谷仓输送到储罐。管网由 NNN 个节点（1≤N≤5001≤N≤5001≤N≤500）组成，每个点都可以作为一组管道的端点。结点 111 是谷仓，结点 NNN 是储罐。MMM 条双向管道中的每一条都连接一对节点，并且都有一个延迟值（牛奶达到管的另一端的用时）和容量值（单位时间内可以稳定通过管道的牛奶量）。多条管道可以连接同一对节点。对于一条连接谷仓与储罐的路径，路径的延迟等于沿途所有管道的延迟之和，路径的容量等于沿途管道最小的容量(因为这是制约牛奶运送的“瓶颈”)。如果约翰通过一条延迟为 LLL、容量为 CCC 的管道运送 XXX 个单位的牛奶，需要的时间为 L+XCL+\frac{X}{C}L+CX​。给出约翰的管网结构，请帮助他选择一条路径，使得他从谷仓到储罐运送 XXX 个单位牛奶的总时间最少。

SPFA 变形。原汁原味，十分经典。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,l,c;};
bool in_que[MAXN];
vector<Edge>adj[MAXN];
int n,m,x,dis[MAXN],lmts[MAXN];
//dis[]:起点到各节点的最小延迟总和
//lmts[]:所有管道的容量
void spfa(int s,int lmt){queue<int>que;dis[s]=0,in_que[s]=true,que.push(s);while(!que.empty()){int u=que.front();in_que[u]=false,que.pop();for(auto[v,l,c]:adj[u])if(c>=lmt&&dis[v]>dis[u]+l){//可以通过且时间更短dis[v]=dis[u]+l;if(!in_que[v])in_que[v]=true,que.push(v);}}
}
int main(){cin>>n>>m>>x;for(int i=1,u,v,l,c;i<=m;i++){cin>>u>>v>>l>>c;adj[u].push_back({v,l,c});adj[v].push_back({u,l,c});lmts[i]=c;}int ans=INF;for(int i=1;i<=m;i++){memset(dis,INF,sizeof(dis));memset(in_que,false,sizeof(in_que));spfa(1,lmts[i]);ans=min(ans,dis[n]+x/lmts[i]);}cout<<ans;return 0;
}

4. Dijkstra

4.1 路径统计

“RP餐厅”（？）的员工素质就是不一般，在齐刷刷的算出同一个电话号码之后，就准备让 HZH，TZY 去送快餐了，他们将自己居住的城市画了一张地图，已知在他们的地图上，有 NNN 个地方，而且他们目前处在标注为 111 的小镇上，而送餐的地点在标注为 NNN 的小镇。除此之外还知道这些道路都是单向的，从小镇 III 到 JJJ 需要花费 D[I,J] 的时间，为了更高效快捷的将快餐送到顾客手中，他们想走一条从小镇 111 到小镇 NNN 花费最少的一条路，但是他们临出发前，撞到因为在路上堵车而生气的 FYY，深受启发，不能仅知道一条路线，万一…于是，他们邀请 FYY 一起来研究起了下一个问题：这个最少花费的路径有多少条？

显然，我们需要新开一个数组 cnt[] 来存储从起点到每个节点的最短路径的数量（即输出的第二个数据）。然后分两种情况：

  • 情况 1：发现一条更短的路径到达节点 vvv（即 dis[v]>dis[u]+w）
    • 更新 dis[v] 为新的最短距离。
    • 重置 cnt[v]=cnt[u]（因为到达 vvv 的最短路径现在只能通过 uuu 实现，路径数量与到达 uuu 的数量相同）。
  • 情况 2：当发现一条与当前最短路径等长的路径（即 dis[v]=dis[u]+w）
    • 累加 cnt[v]+=cnt[u]（到达 vvv 的最短路径又多了 cnt[u] 条，这些路径是通过 uuu 到达 vvv 的）。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
bool vis[MAXN];
vector<Edge>adj[MAXN];
int n,m,dis[MAXN],cnt[MAXN];
void dijkstra(int s){priority_queue<pair<int,int> >pq;dis[s]=0,cnt[s]=1,pq.push({0,s});while(!pq.empty()){auto u=pq.top().second;pq.pop();if(vis[u])continue;vis[u]=true;for(auto[v,w]:adj[u])if(dis[v]>dis[u]+w)dis[v]=dis[u]+w,cnt[v]=cnt[u],pq.push({-dis[v],v});else if(dis[v]==dis[u]+w)cnt[v]+=cnt[u];}
}
int main(){cin>>n>>m;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[u].push_back({v,w});memset(dis,INF,sizeof(dis));dijkstra(1);if(dis[n]==INF)cout<<"No answer";else cout<<dis[n]<<" "<<cnt[n];return 0;
}

4.2 平面上的点

给定平面上的 nnn 个点，定义 (x1,y1)→(x2,y2)(x_1,y_1)\rightarrow(x_2,y_2)(x1​,y1​)→(x2​,y2​) 的费用为它们的最小距离分量，求从 111 号点走到 nnn 号点的最小费用。

很显然，有一个 O(n2)O(n^2)O(n2) 的建图方法：

for(int u=1;u<=n;u++)for(int v=u+1;v<=n;v++){adj[u].push_back({v,min(abs(p[u].x-p[v].x),abs(p[u].y-p[v].y))});adj[v].push_back({u,min(abs(p[u].x-p[v].x),abs(p[u].y-p[v].y))});}

但可以考虑投影优化。

首先，将平面上的点 (x,y)(x, y)(x,y) 投射到 xxx 轴上，得到投影点 (x,0)(x, 0)(x,0)，两点的 xxx 轴投影距离为 ∣x1−x2∣|x_1 - x_2|∣x1​−x2​∣（即横向距离）；然后，将平面上的点 (x,y)(x, y)(x,y) 投射到 yyy 轴上，得到投影点 (0,y)(0, y)(0,y)，两点的 yyy 轴投影距离为 ∣y1−y2∣|y_1 - y_2|∣y1​−y2​∣（即纵向距离）。

接下来，利用投影的相邻性质，即在同一投影轴上（如 xxx 轴），任意两个非相邻投影点的距离，等于它们之间所有相邻投影点的距离之和。

然后，再利用 Dijkstra 等其他最短路算法的性质，我们知道，每次在计算起点到当前节点的距离的时候，都会处理出真正的最短距离。因此我们只需要把 ∣x1−x2∣|x_1-x_2|∣x1​−x2​∣ 和 ∣y1−y2∣|y_1-y_2|∣y1​−y2​∣ 一起放入邻接矩阵即可。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
struct Point{int x,y,idx;}p[MAXN];
bool vis[MAXN];
int n,m,s,t,dis[MAXN];
vector<Edge>adj[MAXN];
bool cmpx(Point p1,Point p2){return p1.x<p2.x;}
bool cmpy(Point p1,Point p2){return p1.y<p2.y;}
void dijkstra(int s){priority_queue<pair<int,int> >pq;//{-dis[u],u}dis[s]=0,pq.push({0,s});while(!pq.empty()){auto u=pq.top().second;pq.pop();if(vis[u])continue;vis[u]=true;for(auto[v,w]:adj[u])if(dis[v]>dis[u]+w)dis[v]=dis[u]+w,pq.push({-dis[v],v});}
}
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y,p[i].idx=i;sort(p+1,p+n+1,cmpx);for(int i=1;i<n;i++){adj[p[i].idx].push_back({p[i+1].idx,p[i+1].x-p[i].x});adj[p[i+1].idx].push_back({p[i].idx,p[i+1].x-p[i].x});}sort(p+1,p+n+1,cmpy);for(int i=1;i<n;i++){adj[p[i].idx].push_back({p[i+1].idx,p[i+1].y-p[i].y});adj[p[i+1].idx].push_back({p[i].idx,p[i+1].y-p[i].y});}memset(dis,INF,sizeof(dis));dijkstra(1);cout<<dis[n];return 0;
}

4.3 邀请函

在电视时代，没有多少人观看戏剧表演。 剧场老板意识到了这一事实，他想宣传剧院，尤其是古典的喜剧片。
他已经打印了邀请函和所有必要的信息和计划。许多学生被雇来分发这些邀请函。每个学生被指定了一个确切的公共汽车站，他或她将留在那里一整天，邀请人们观看戏剧表演。
这里的公交系统是非常特殊的：共有 nnn 个站点和 mmm 个线路，所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。
学生每天早上从总部所在的 111 号站点出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候，所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。

见 3.1 奶牛派对（就在本篇博客）。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
const int INF=0x3f3f3f3f;
struct Edge{int v,w;};
bool vis[MAXN];
vector<Edge>adj[2][MAXN];
int n,m,dis[MAXN],ans[MAXN];
void dijkstra(int s,int rev){memset(dis,INF,sizeof(dis));memset(vis,false,sizeof(vis));priority_queue<pair<int,int> >pq;dis[s]=0,pq.push({0,s});while(!pq.empty()){auto u=pq.top().second;pq.pop();if(vis[u])continue;vis[u]=true;for(auto[v,w]:adj[rev][u])if(dis[v]>dis[u]+w)dis[v]=dis[u]+w,pq.push({-dis[v],v});}
}
int main(){cin>>n>>m;for(int i=1,u,v,w;i<=m;i++)cin>>u>>v>>w,adj[0][u].push_back({v,w}),adj[1][v].push_back({u,w});dijkstra(1,0);for(int i=1;i<=n;i++)ans[i]=dis[i];dijkstra(1,1);long long ret=0;for(int i=1;i<=n;i++)ans[i]+=dis[i],ret+=ans[i];cout<<ret;return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/web/89879.shtml
繁体地址，请注明出处：http://hk.pswp.cn/web/89879.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

“融合进化，智领未来”电科金仓引领数字化转型新纪元

“融合进化，智领未来”电科金仓引领数字化转型新纪元

一、融合进化 智领未来电科金仓2025产品发布会重磅开启&#xff01; 7月15日&#xff0c;以“融合进化 智领未来”为主题的电科金仓2025产品发布会在北京举办。产品发布会上展示了四款代表未来数字化趋势的创新性产品。这些产品不仅涵盖了数据库技术&#xff0c;还涉及到数据集…
阅读更多...
常规笔记本和加固笔记本的区别

常规笔记本和加固笔记本的区别

在现代科技产品中&#xff0c;笔记本电脑因其便携性和功能性被广泛应用。根据使用场景和需求的不同&#xff0c;笔记本可分为常规笔记本和加固笔记本&#xff0c;二者在多个方面存在显著区别。适用场景是区分二者的重要标志。常规笔记本主要面向普通消费者和办公人群&#xff0…
阅读更多...
Shell 脚本编程全面学习指南

Shell 脚本编程全面学习指南

前言Shell 脚本编程是 Linux 和 Unix 系统管理、自动化任务的核心工具之一。通过 Shell 脚本&#xff0c;你可以自动化重复性操作、简化复杂流程、提高系统管理效率&#xff0c;甚至构建完整的自动化运维工具。本文将带你从基础到进阶&#xff0c;全面学习 Shell 脚本编程&…
阅读更多...
DelayQueue延迟队列的使用

DelayQueue延迟队列的使用

1、DelayQueue简介 DelayQueue 也是 Java 并发包&#xff08;java.util.concurrent&#xff09;中的一个特殊队列,用于在指定的延迟时间之后处理元素。 DelayQueue的一些关键特性&#xff1a; 延迟元素处理&#xff1a;只有当元素的延迟时间到期时&#xff0c;元素才能被取出…
阅读更多...
QT6 源，七章对话框与多窗体（6） 颜色对话框 QColorDialog ：本类的属性，信号函数，静态成员函数，以及源代码

QT6 源，七章对话框与多窗体（6） 颜色对话框 QColorDialog ：本类的属性，信号函数，静态成员函数，以及源代码

&#xff08;1&#xff09;本类的继承关系如下 &#xff1a;&#xff08;2&#xff09; 对于本标准颜色对话框来讲&#xff0c;学会使用其静态函数以获取到颜色就足够了。&#xff08;3&#xff09; 开始学习本类的静态成员函数 &#xff1a;&#xff08;4&#xff09;测试一下…
阅读更多...
金仓数据库：融合进化，智领未来——2025年数据库技术革命的深度解析

金仓数据库：融合进化，智领未来——2025年数据库技术革命的深度解析

引言 在数字中国战略的推动下&#xff0c;数据库作为数字经济的基础设施&#xff0c;正经历着前所未有的技术重构。2025年7月15日&#xff0c;电科金仓以"融合进化&#xff0c;智领未来"为主题&#xff0c;发布了新一代数据库产品矩阵&#xff0c;标志着国产数据库在…
阅读更多...
【人工智能99问】卷积神经网络（CNN）的结构和原理是什么？(10/99)

【人工智能99问】卷积神经网络（CNN）的结构和原理是什么？(10/99)

文章目录卷积神经网络&#xff08;CNN&#xff09;的结构及原理一、CNN的核心结构1. 输入层&#xff08;Input Layer&#xff09;2. 卷积层&#xff08;Convolutional Layer&#xff09;2. 卷积层的核心机制&#xff1a;局部感受野与权值共享3. 池化层&#xff08;Pooling Laye…
阅读更多...
CCF编程能力等级认证GESP—C++7级—20250628

CCF编程能力等级认证GESP—C++7级—20250628

CCF编程能力等级认证GESP—C7级—20250628单选题&#xff08;每题 2 分&#xff0c;共 30 分&#xff09;判断题&#xff08;每题 2 分&#xff0c;共 20 分&#xff09;编程题 (每题 25 分&#xff0c;共 50 分)线图调味平衡单选题&#xff08;每题 2 分&#xff0c;共 30 分&…
阅读更多...
《Python 类设计模式：属性分类（类属性 VS 实例属性）与方法类型（实例 / 类 / 静态）详解》

《Python 类设计模式：属性分类（类属性 VS 实例属性）与方法类型（实例 / 类 / 静态）详解》

Python 类和对象&#xff1a;从 "图纸" 到 "实物" 的编程思维面向对象编程&#xff08;Object-Oriented Programming&#xff0c;简称OOP &#xff09;是一种通过组织对象来编程的方法。1.初识类和对象&#xff1a;用生活例子看透核心概念1.1类-class物与类…
阅读更多...
Eureka服务端启动

Eureka服务端启动

目录 1、相关文章 2、创建eureka-server子工程 3、父工程build.gradle引入版本依赖管理 4、子工程build.gradle引入依赖 5、将main重命名为EurekaApplication并修改代码 6、添加application.yml文件 7、启动工程并访问 8、访问界面如下 9、 完整目录结构 1、相关文章 …
阅读更多...
AWS Partner: Sales Accreditation (Business)

AWS Partner: Sales Accreditation (Business)

AWS Partner: Sales Accreditation &#xff08;Business&#xff09;云概念和AWS云计算什么是云计算&#xff1f;计算的演变趋势云计算部署模型AWS 客户采用的模式为什么客户选择AWSAWS竞争优势高可用的全球基础设施AWS服务服务广度和深度AWS产品和服务服务类别AWS解决方案库A…
阅读更多...
深入理解设计模式之中介者模式：解耦对象交互的利器

深入理解设计模式之中介者模式：解耦对象交互的利器

为什么需要中介者&#xff1f;在软件开发中&#xff0c;我们经常会遇到对象之间需要相互通信的场景。当系统规模较小时&#xff0c;对象直接相互引用并通信可能不会带来太大问题。但随着系统复杂度增加&#xff0c;对象间的交互关系会变得错综复杂&#xff0c;形成一个复杂的网…
阅读更多...
从 0 安装 Label Studio：搭建可后台运行的数据标注平台（systemd 实践

从 0 安装 Label Studio：搭建可后台运行的数据标注平台（systemd 实践

本文将介绍如何使用 pip 安装 Label Studio&#xff0c;并通过 systemd 实现开机自启与后台运行&#xff0c;适用搭建个人项目的数据标注平台。 一、Label Studio 简介 Label Studio 是一个开源、跨模态的数据标注工具&#xff0c;支持文本、图像、音频、视频、HTML等多种类型…
阅读更多...
【数据结构】链表（linked list）

【数据结构】链表（linked list）

目录 一、链表的介绍 二、单链表 1. 单链表的初始化 2. 单链表的插入 &#xff08;1&#xff09;动态申请一个节点 &#xff08;2&#xff09;头插法 &#xff08;3&#xff09;尾插法 &#xff08;4&#xff09;按照位置来插入 &#xff08;5&#xff09;在地址之前插…
阅读更多...
反序列化漏洞1-PHP序列化基础概念（0基础超详细）

反序列化漏洞1-PHP序列化基础概念（0基础超详细）

一.PHP序列化基础概念首先当我们看到反序列化漏洞这个概念&#xff0c;我们的第一个问题是什么是反序列化&#xff1f;那么我们要知道什么是反序列化就要知道什么是序列化。序列化就是可以将一个对象压缩并格式化成字符串&#xff0c;可以将该对象保存下来&#xff0c;以便存储…
阅读更多...
【微服务】Ocelot微服务网关

【微服务】Ocelot微服务网关

目录 一、目的 二、Ocelot介绍 三、.Net中使用Ocelot搭建网关服务 3.1 搭建网关Ocelot步骤 3.1.1、创建Net7 WebApi服务 3.1.2、Nuget引入-Ocelot程序包&#xff08;版本&#xff1a;19.0.2&#xff09; 3.1.3、配置中间件和IOC注册 3.1.4 配置文件编辑Ocelot网关配置信…
阅读更多...
零基础入门：用按键精灵实现视频自动操作（附完整脚本）

零基础入门：用按键精灵实现视频自动操作（附完整脚本）

摘要&#xff1a;本文手把手教你编写视频平台的自动化脚本&#xff0c;涵盖点击、循环、防检测等核心技巧&#xff0c;无需编程基础&#xff0c;轻松实现自动播放/点赞/跳过广告。&#xff08;使用按键精灵2024版演示&#xff09; 一、应用场景 自动化操作&#xff1a;自动跳过…
阅读更多...
AI(学习笔记第六课) 使用langchain进行AI开发 load documents(csv和文件夹)

AI(学习笔记第六课) 使用langchain进行AI开发 load documents(csv和文件夹)

文章目录AI(学习笔记第六课) 使用langchain进行AI开发 load documents(csv和文件夹)学习内容&#xff1a;1.load documents&#xff08;csv&#xff09;1.1 学习url1.2 load csv文件1.2.1 默认load1.2.2 csv文件内容1.2.2 执行csv文件的load1.3 Customizing the CSV parsing an…
阅读更多...
企业运维实战：Jenkins 依赖 JDK21 与应用需 JDK1.8 共存方案（含流水线配置）

企业运维实战：Jenkins 依赖 JDK21 与应用需 JDK1.8 共存方案（含流水线配置）

前言&#xff1a;在企业运维中&#xff0c;“工具升级”与“业务兼容”的平衡始终是核心挑战。近期我们遇到一个典型场景&#xff1a;Jenkins 升级到 2.450 版本后&#xff0c;强制要求 JDK21 运行环境&#xff1b;但开发团队的应用程序因框架依赖&#xff0c;必须使用 JDK1.8 …
阅读更多...
爬虫小知识三：selenium库

爬虫小知识三：selenium库

前言 selenium 库是一种用于 Web 应用程序测试的工具&#xff0c;它可以驱动浏览器执行特定操作&#xff0c;自动按照脚本代码做出单击、输入、打开、验证等操作&#xff0c;支持的浏览器包括 IE、Firefox、Safari、Chrome、Opera 等。 与 requests 库不同的是&#xff0c;se…
阅读更多...
最新文章

Copyright @ 2022~2023