链接：https://vjudge.net/problem/POJ-1502
题意：
n个点，从1号向开始选择任意个结点发送信息，下一个结点接收到信息后可再向任意个结点发送。
同时发送信息有时间代价。代价有邻接矩阵给出。只给出坐下全部，x为不连通。
同时为无向的。即a->b == b->a。
求每个结点都接受到信息的最小时间代价。
思路：
Dijkstra，求Dis数组中的最大值
代码：
#include <iostream>
#include <memory.h>
#include <string>
#include <istream>
#include <sstream>
using namespace std;
const int MAXN = 100+10;
int Map[MAXN][MAXN];
int Dis[MAXN];
int Vis[MAXN];
int main()
{
int n;
scanf("%d",&n);
for (int i = 1;i<=n;i++)
for (int j = 1;j<=n;j++)
if (i == j)
Map[i][j] = 0;
else
Map[i][j] = 999999;
for (int i = 2;i<=n;i++)
for (int j = 1;j<i;j++)
{
string x;
cin >> x;
if (x[0] != 'x')
{
istringstream iss(x);
int num;
iss >> num;
Map[i][j] = Map[j][i] = num;
}
}
for (int i = 1;i<=n;i++)
Dis[i] = Map[1][i];
Vis[1] = 1;
for (int i = 1;i<=n;i++)
{
int w = -1,small = 999999;
for (int j = 1;j<=n;j++)
if (Vis[j] == 0&&Dis[j] < small)
{
w = j;
small = Dis[j];
}
Vis[w] = 1;
for (int j = 1;j<=n;j++)
{
if (Vis[j] == 0)
{
Dis[j] = min(Dis[j],Dis[w]+Map[w][j]);
//cout << Dis[j] << ' ' << Dis[w] + Map[w][j] << endl;
}
}
}
int sum = 0;
for (int i = 2;i<=n;i++)
sum = max(sum,Dis[i]);
cout << sum << endl;
return 0;
}
/*
4
10
x 10
x x 10
*/
转载于:https://www.cnblogs.com/YDDDD/p/10274877.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/101169.html原文链接：https://javaforall.net
