POJ-1502 MPI Maelstrom 迪杰斯特拉+题解

题意

解题思路

这个可以用迪杰斯特拉来求第一台机器到其他所有机器传输消息的时间，然后答案就是到其他机器所需时间的最大值。

下面给了两种

代码实现

//n方，没有优化那种

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=1e2+7;

const int inf=0x3f3f3f3f;

int mp[maxn][maxn];

int dis[maxn];

int vis[maxn];

int n;

void init()

{

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

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

			mp[i][j]= i==j? 0:inf;

	fill(dis+1, dis+n+1, inf);

	fill(vis+1, vis+n+1, 0);

}

void dij()

{

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

		dis[i]=mp[1][i];

	vis[1]=1;

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

	{

		int tmp=inf, k;

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

		{

			if(!vis[j] && dis[j]<tmp)

			{

				tmp=dis[j];

				k=j;

			}

		}

		vis[k]=1;

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

		{

			if(!vis[j] && dis[j] > dis[k]+mp[k][j] )

			{

				dis[j]=dis[k]+mp[k][j];

			}

		}

	}

}

int main()

{

	while(scanf("%d", &n)!=EOF)

	{

		init();

		char num[10];

		int tmp, len;

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

		{

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

			{

				scanf("%s", num);

				if(num[0]=='x') continue;

				tmp=0;

				len=strlen(num);

				for(int k=0; k<len; k++)

				{

					tmp=tmp*10+num[k]-'0';

				}

				mp[i][j]=tmp;

				mp[j][i]=tmp;

			}

		}

		dij();

		int ans=0;

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

		{

			ans=max(ans, dis[i]);

		}

		printf("%d\n", ans);

	}

	return 0;

}

//使用优先队列进行优化

#include<cstdio>

#include<cstring>

#include<vector>

#include<queue>

#include<algorithm>

using namespace std;

const int inf=0x3f3f3f3f;

const int maxn=1e3+7;

const int maxe=1e6+7;

struct headnode{

	int d, u;

	bool friend operator < (const headnode a, const headnode b)

	{

		return a.d > b.d;

	}

};

struct edge

{

	int to, cost;

};

int n;

int dis[maxn];

int vis[maxn];

vector<edge> g[maxn];

priority_queue<headnode> que;

void init()

{

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

	{

		dis[i]=inf;

		vis[i]=0;

		g[i].clear();

	}

	while(!que.empty()) que.pop();

}

void dij(int s)

{

	edge e;

	dis[s]=0;

	headnode head={0, s}, tmp;

	que.push(head);

	while(!que.empty())

	{

		head=que.top();

		que.pop();

		if(vis[head.u]==1)continue;

		vis[head.u]=1;

		for(int i=0; i<g[head.u].size(); i++)

		{

			e=g[head.u][i];

			if(dis[e.to] > dis[head.u]+e.cost)

			{

				dis[e.to]=dis[head.u]+e.cost;

				tmp.d=dis[e.to];

				tmp.u=e.to;

				que.push(tmp);

			}

		}

	}

}

int main()

{

	while(scanf("%d", &n)!=EOF)

	{

		init();

		int c;

		edge e;

		char str[10];

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

		{

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

			{

				scanf("%s", str);

				if(str[0]=='x') continue;

				c=atoi(str);

				e.cost=c;

				e.to=j;

				g[i].push_back(e);

				e.to=i;

				g[j].push_back(e);

			}

		}

		dij(1);

		int ans=0;

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

			ans=max(dis[i], ans);

		printf("%d\n", ans);

	}

	return 0;

}

END