POJ 1502

本文主要是介绍POJ 1502，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一道水题就这么不幸贡献了两发WA，原因在于没有审题啊。关于输出要求，人家明确说了第一个到其他的距离

题目信息量略大（低情商：废话过多），很简单的最短路，因为没有仔细读题错误理解成了所有节点对最短路径的最大值。采取了floyd算法，不过时间复杂度很小，并无大问题。

此外，初始化，以及对于输入数据读取都非常重要。

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <string>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int maxn= 105;
const int INF= 0x3f3f3f3f;

int A[maxn][maxn];

int main(int argc, char const *argv[])
{
	int n, ans= 0;
	scanf("%d", &n);
	string in;
	for (int i= 1; i<= n; ++i){
		for (int j= 1; j< i; ++j){
			cin>>in;
			int num;
			if ("x"== in){
				num= INF;
			}
			else{
				sscanf(in.c_str(), "%d", &num);
			}
			A[i][j]= A[j][i]= num;
		}
		A[i][i]= 0;
	}

	for (int k= 1; k<= n; ++k){
		for (int i= 1; i<= n; ++i){
			for (int j= 1; j<= n; ++j){
				A[i][j]= min(A[i][k]+A[k][j], A[i][j]);
			}
		}
	}
	for (int i= 1; i<= n; ++i){
		for (int j= 1; j<= n; ++j){
			ans= max(ans, A[1][j]);
		}
	}

	cout<<ans<<endl;

	return 0;
}

这篇关于POJ 1502的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！