信使(msner)（信息学奥赛一本通- P1376）四种做法-平芜编程栈

【题目描述】

战争时期，前线有n个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。指挥部设在第一个哨所。当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。直至所有n个哨所全部接到命令后，送信才算成功。因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他k个哨所有通信联系的话，这个哨所内至少会配备k个信使）。

现在总指挥请你编一个程序，计算出完成整个送信过程最短需要多少时间。

【输入】

第1行有两个整数n和m，中间用1个空格隔开，分别表示有n个哨所和m条通信线路,且1≤n≤100。

第2至m+1行：每行三个整数i、j、k，中间用1个空格隔开，表示第i个和第j个哨所之间存在通信线路，且这条线路要花费k天。

【输出】

一个整数，表示完成整个送信过程的最短时间。如果不是所有的哨所都能收到信，就输出-1。

【输入样例】

4 4 1 2 4 2 3 7 2 4 1 3 4 6

【输出样例】

0. 前言

《信使》是一道经典的图论入门题。题目要求计算从指挥部（源点 1）发出命令，到最后一个哨所收到命令所需的最短时间。

核心模型转化：

单源最短路：计算点 1 到所有点i的最短距离dis[i]。
木桶效应：由于此时所有信使同时出发，完成任务的时间取决于最远的那个哨所。即求 MAX i从1-n {dis[i]}。
连通性判定：如果存在某个点dis[i]仍为无穷大，说明无法送达，输出 -1。

针对这道数据范围N<=100的题目，以下展示并分析四种不同的实现思路

1. 解法一：Floyd-Warshall 算法

思路解析：

利用O(N^3)的动态规划思想，通过中转点k松弛任意两点(i, j)之间的距离。虽然效率较低，但对于 N=100的数据规模绰绰有余。

学生隐患点：

在处理邻接矩阵存图时，代码如果直接使用了赋值语句 g[u][v] = w。若测试数据中两点间存在多条线路（重边），这种写法会保留最后读入的那条边，而非最短边，可能导致错误。

完整代码

//想到一个点，这题就迎刃而解了，就是求完最短路后，去找源点到其他所有点中所需时间中最大的那个时间 //这就是送信过程最短时间，因为不可能有点到源点所需时间更长，因为指挥所是同时派出多个信使的 //这个想不到就会很复杂 我一开始也没想到 直接想到广搜了，写完广搜才想到那本质上走完全程就是走去最远的点 //floyd #include <iostream> #include <cstring> using namespace std; int n,m; int g[150][150]; void floyd(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(g[i][j]>g[i][k]+g[k][j]) g[i][j]=g[i][k]+g[k][j]; } } } } int main(){ cin>>n>>m;//n个哨所 m条通信线路 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ g[i][j]=0x3f3f3f3f;//初始化临接矩阵哨所与哨所之间距离为无穷 } } for(int i=1;i<=n;i++) g[i][i]=0;//初始化每个哨所与自己的距离为0 //存图 for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; g[u][v] = g[v][u] = min(g[u][v], w); //双向 且需要处理重边 } floyd();//将每个点到其他点的最短路求出来 int ma=0; for(int i=1;i<=n;i++) ma=max(ma,g[1][i]); if(ma!=0x3f3f3f3f) cout<<ma; else cout<<"-1"; return 0; }

2. 解法二：Floyd + BFS 松弛（混合写法）

思路解析：

这是一种较为特殊的混合写法。因为我一开始第一思路是这个，代码首先运行了 floyd() 计算出所有最短路径，随后又使用队列进行了一次基于邻接矩阵的广度优先搜索（BFS）松弛操作。

完整代码

//这是一开始想到的广搜的办法，先floyd求最短路，然后广搜，就很复杂hhh #include <iostream> #include <queue> using namespace std; int n,m; int g[150][150]; int vis[150];//vis[i]表示从指挥部到第i个哨所所需时间 queue<int> q; void floyd(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(g[i][j]>g[i][k]+g[k][j]) g[i][j]=g[i][k]+g[k][j]; } } } } void bfs(int k){ vis[k]=0;//指挥部到自己时间为0 q.push(k);//起点入队 while(!q.empty()){ int tmp=q.front();//访问队首元素 q.pop();//队首出队 for(int i=1;i<=n;i++){//遍历所有哨所，看是否与当前tmp哨所之间有路 //如果不是tmp哨所自身且与tmp哨所之间有路 //且（从起点走到tmp哨所所需时间+tmp走到i所需时间）小于从起点走到i已记录时间 //就更新vis[i]，并将i入队 if(i!=tmp && g[tmp][i]!=0x3f3f3f3f &&vis[tmp]+g[tmp][i]<vis[i]){ q.push(i); vis[i]=vis[tmp]+g[tmp][i]; } } } } int main(){ cin>>n>>m;//n个哨所 m条通信线路 for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ g[i][j]=0x3f3f3f3f;//初始化临接矩阵哨所与哨所之间距离为无穷 } } for(int i=1;i<=n;i++) g[i][i]=0;//初始化每个哨所与自己的距离为0 //存图 for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; g[u][v]=w;//线路是双向的 g[v][u]=w; } floyd();//将每个点到其他点的最短路求出来 for(int i=1;i<=n;i++) vis[i]=0x3f3f3f3f;//初始化指挥部到每个哨所时间为无穷 bfs(1);//然后进行广搜 int mi=0; for(int i=1;i<=n;i++){//广搜后到所有点的最大时间就是送完全程的最短时间 mi=max(mi,vis[i]);//找出最大时间 } if(mi==0x3f3f3f3f) cout<<-1;//如果最短时间为无穷，代表不是所有哨所都能收到信 else cout<<mi;//不为无穷，就输出时间 return 0; }

3. 解法三：Dijkstra 邻接表+ 堆优化

思路解析：

使用邻接表存储图结构，配合优先队列（小根堆）实现 Dijkstra 算法。这是处理非负权图最短路问题的标准解法，时间复杂度为 O(M log N)。对于稀疏图或点数较多的情况，效率远优于 Floyd。

完整代码

//dijkstra临接表+堆优化 #include <iostream> #include <queue> using namespace std; int n,m; int h[150]; int vtex[30000];//最多100个哨所，则最多有4450条线路，但是双向，所以9900，开30000肯定够 int nxt[30000]; int wt[30000]; int dis[150];//每个哨所到指挥所的距离 int idx; int vis[150];//记录每个哨所是否被点亮即出队过 struct node{ int id;//表示是几号哨所 int w;//到指挥所的距离 //重载运算符，将默认大根堆修改为小根堆 friend bool operator <(node a,node b){ return a.w>b.w; } }; priority_queue<node> q; void dijkstra(int s){ dis[s]=0;//指挥所到自己的距离为0 node tmp; tmp.id=s; tmp.w=0; q.push(tmp);//指挥所（源点）入队 while(!q.empty()){ tmp=q.top();//访问队首元素 q.pop();//队首出队 int nid=tmp.id; if(vis[nid]==1) continue;//懒惰删除 如果tmp已经出队过就跳过 vis[nid]=1;//否则就标记出队过 int p=h[nid];//tmp的头指针 while(p!=-1){ //如果tmp这个邻接点vtex[p]没有出队过 if(vis[vtex[p]]==0){ //如果tmp的邻接点到源点（指挥所）的距离大于tmp到源点的距离+tmp到该邻接点的距离，就更新并入队 if(dis[vtex[p]]>dis[nid]+wt[p]){ dis[vtex[p]]=dis[nid]+wt[p]; //只有tmp的邻接点到源点的距离发生更新后，才会入队 q.push({vtex[p],dis[vtex[p]]}); } } p=nxt[p];//更新指针 } } } void addedge(int u,int v,int w){ vtex[idx]=v; nxt[idx]=h[u]; wt[idx]=w; h[u]=idx++; } int main(){ cin>>n>>m;//n个哨所 m条通信线路 memset(h,-1,sizeof(h));//初始化头指针数组 //邻接表存图 for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; addedge(u,v,w);//通信线路是双向的 addedge(v,u,w); } for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f;//初始化所有哨所到指挥所的距离为无穷 dijkstra(1); int ma=0;//最短时间 for(int i=1;i<=n;i++){//找到所有哨所中到指挥所时间最长的所需时间 ma=max(ma,dis[i]); } //输出邻接表检查一下 //for(int i=1;i<=n;i++){ // cout<<i<<":"; // int p=h[i]; // while(p!=-1){ // cout<<vtex[p]<<" "<<wt[p]<<" "; // p=nxt[p]; // } //} //如果最长时间为无穷，说明有点不可达 if(ma==0x3f3f3f3f) cout<<-1; else cout<<ma; return 0; }

4. 解法四：SPFA 算法

思路解析：

SPFA 是 Bellman-Ford 的队列优化版本。通过 is_used 数组标记节点是否在队列中，仅对发生松弛的节点进行入队操作。

完整代码：

//spfa #include <iostream> #include <queue> using namespace std; queue<int> q; int n,m; int h[150]; int vtex[30000]; int nxt[30000]; int wt[30000]; int idx; int dis[150]; bool is_used[150];//标记每个节点是否在队中 void spfa(int s){ dis[s]=0;//源点到自己的距离为0 q.push(s); is_used[s]=1; while(!q.empty()){ int tmp=q.front();//访问队首元素 q.pop();//队首出队 is_used[tmp]=0;//出队后标记重新打为0 int p=h[tmp];//tmp的头指针 while(p!=-1){//访问tmp的所有邻接点 //如果邻接点到源点的距离大于（tmp到源点距离+tmp到该邻接点距离） //就更新邻接点到源点距离，并判断该邻接点是否在队列中，如果不在，就入队 if(dis[vtex[p]]>dis[tmp]+wt[p]){ dis[vtex[p]]=dis[tmp]+wt[p]; if(is_used[vtex[p]]==0){//如果不在队列中 q.push(vtex[p]);//就入队 is_used[vtex[p]]=1;//并打上标记 } } p=nxt[p]; } } } void addedge(int u,int v,int w){ vtex[idx]=v; nxt[idx]=h[u]; wt[idx]=w; h[u]=idx++; } int main(){ cin>>n>>m; memset(h,-1,sizeof(h));//初始化头指针数组 for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f;//初始化dis数组为无穷大 //邻接表存图 for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; addedge(u,v,w); addedge(v,u,w); } spfa(1); int ma=0;//最短送信时间 for(int i=1;i<=n;i++){ ma=max(ma,dis[i]); } if(ma==0x3f3f3f3f) cout<<-1; else cout<<ma; return 0; }