比赛 20110730 评测结果 AAAAAAAAAA
题目名称 线段 最终得分 100
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-30 09:47:44
显示代码纯文本
#include <fstream>

#define I_F "line.in"
#define O_F "line.out"
#define MAXn (300+1)

using namespace std;

int n;
short map[MAXn][MAXn];

ifstream fin(I_F);
ofstream fout(O_F);

inline void Clear();
void Input();
bool Floyd();
void Output(bool);

int main()
{
	int donny;
	fin>>donny;
	for (int kilnyy=0; kilnyy<donny; kilnyy++)
	{
		Clear();
		Input();
		Output(Floyd());
	}
	fin.close();
	fout.close();
}

inline void Clear()
{
	for (int i=0; i<MAXn; i++)
		for (int j=0; j<MAXn; map[i][j++]=0);
}

void Input()
{
	int m,x,y,k;
	fin>>n>>m;
	for (int i=0; i<m; i++)
	{
		fin>>x>>y>>k;
		map[x][y]=(k==0)?1:-1;
		map[y][x]=map[x][y];
	}
}

bool Floyd()
{
	for (int k=1; k<=n; k++)
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++)
				if ((map[i][k]!=0)&&(map[k][j]!=0))
				{
					if (map[i][j]==0)
						map[i][j]=map[i][k]*map[k][j];
					else
						if (map[i][j]!=map[i][k]*map[k][j])
							return false;
				}
	return true;
}

void Output(bool f)
{
	if (!f)
		fout<<"No Answer\n";
	else
		if (map[1][n]==0) fout<<"2\n";
		else if (map[1][n]==-1) fout<<"1\n";
		else fout<<"0\n";
}