POJ - 1502 MPI Maelstrom

​​​​​​MPI Maelstrom - POJ 1502 - Virtual Judge (csgrandeur.cn)

涉及算法:快读,dijkstra,链式前向星

快读模板 - AcWing

POJ 1502 - MPI Maelstrom（链式前向星 + dijkstra模板题）

题意:从司令部可以走出若干个成员,每个成员去给其他营的保信,问什么时候所有营知道消息

思路:

dijkstra跑一遍最短路,求出所有点到源点的距离,再把其中最大的距离拿出来就是所有营地都接收到信息的时间

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+50,M=1,inf=0x3f3f3f3f;
int h[N],e[N],ne[N],w[N],idx;
int dist[N];
bool st[N];
int n;
inline int read()
{char c=getchar();if(c=='x') return inf;int res=0;while(!isdigit(c)){c=getchar();if(c=='x') return inf;}while(isdigit(c)) res=(res<<3)+(res<<1)+(c^48),c=getchar();return res;
}
void add(int a,int b,int c)
{e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
void dijkstra(int u)
{memset(dist,0x3f,sizeof(dist));dist[u]=0;for(int i=0;i<n;i++){int t=-1;for(int j=1;j<=n;j++){if(st[j]==false&&(t==-1||dist[t]>dist[j])){t=j;}}st[t]=true;for(int j=h[t];j!=-1;j=ne[j]){int now=e[j];dist[now]=min(dist[now],dist[t]+w[j]);}}
}
int main()
{n=read();memset(h,-1,sizeof(h));for(int i=2;i<=n;i++){for(int j=1;j<i;j++){int val=read();if(val==0x3f3f3f3f) continue;add(i,j,val);add(j,i,val); }}dijkstra(1);int ans=0;for(int i=2;i<=n;i++)ans=max(ans,dist[i]);cout<<ans<<endl;return 0;
}