AcWing 1128. 信使

战争时期，前线有 n个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。

信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。

指挥部设在第一个哨所。当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。

当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。

信在一个哨所内停留的时间可以忽略不计。

直至所有n个哨所全部接到命令后，送信才算成功。

因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他k个哨所有通信联系的话，这个哨所内至少会配备 kk个信使）。

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

#include<bits/stdc++.h>

#define N 1000000

using namespace std;

priority_queue<pair<int ,int >,vector<pair<int ,int > >,greater<pair<int ,int > > > dl;

int head[N],to[N],vis[N],net[N];

int d[N],f[N];

int cut,n,m,ans;

void add(int from, int t,int v){net[++cut]=head[from],to[cut]=t,vis[cut]=v,head[from]=cut;};

void dijkstra(int x)

{

    dl.push(make_pair(0,x));

    d[x]=0;

    while(dl.size())

    {

        x=dl.top().second;dl.pop();

        if(f[x]==1)continue;f[x]=1;

        for(int i=head[x];i;i=net[i])

        {

            int y=to[i];

            if(d[x]+vis[i]<d[y])

            {

                d[y]=d[x]+vis[i];

                dl.push(make_pair(d[y],y));

            }

        }

    }

}

int main()

{

    cin>>m>>n;

    memset(d,0x3f3f3f3f,sizeof d);

    for(int i=1;i<=n;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        add(x,y,z);add(y,x,z);

    }

    dijkstra(1);

    for(int i=1;i<=m;i++){ans=max(ans,d[i]);}

    if(ans==0x3f3f3f3f)ans=-1;

    cout<<ans;

    return 0;

}

巴特西

AcWing 1128. 信使

最新文章

热门文章