不知道取什么标题了
要考试了,于是就手动模拟了一个队列,毕竟是为了复习
题目描述
战争时期,前线有 n 个哨所,每个哨所可能会与其他若干个哨所之间有通信联系。
信使负责在哨所之间传递信息,当然,这是要花费一定时间的(以天为单位)。
指挥部设在第一个哨所。
当指挥部下达一个命令后,指挥部就派出若干个信使向与指挥部相连的哨所送信。
当一个哨所接到信后,这个哨所内的信使们也以同样的方式向其他哨所送信。信在一个哨所内停留的时间可以忽略不计。
直至所有 n 个哨所全部接到命令后,送信才算成功。
因为准备充足,每个哨所内都安排了足够的信使(如果一个哨所与其他 k 个哨所有通信联系的话,这个哨所内至少会配备 k 个信使)。
现在总指挥请你编一个程序,计算出完成整个送信过程最短需要多少时间。
样例
4 4
1 2 4
2 3 7
2 4 1
3 4 6
C++ 代码
#include<bits/stdc++.h>
#define N 2000
using namespace std;
int cnt=0,minn=0,n,m;
int vis[N],q[N],f[N],head[N];
struct ed{
int pre;
int w;
int nex;
}a[N];
void ad_(int x,int y,int z){
cnt++;
a[cnt].pre=y;
a[cnt].w=z;
a[cnt].nex=head[x];
head[x]=cnt;
}
void spfa(int s){
f[s]=0;
vis[s]=1;
int ha=1,ta=1;
q[ta]=s;
ta++;
while(ha<ta){
int k=q[ha];
for (int i=head[k];i;i=a[i].nex){
int u=a[i].pre,v=a[i].w;
if(f[u]>f[k]+v){
f[u]=f[k]+v;
q[ta]=u;
ta++;
}
}
vis[k]=0;
ha++;
}
}
int main(){
memset(f,0x3f,sizeof(f));
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
ad_(x,y,z);
ad_(y,x,z);
}
spfa(1);
for (int i=1;i<=n;i++) if(f[i]>minn) minn=f[i];
if(minn==0x3f3f3f3f) puts("-1");
else printf("%d",minn);
return 0;
}