记录编号	26284	评测结果	AAAAAAAAAAAAAAAAW
题目名称	网络探测	最终得分	94
用户昵称	Citron酱	是否通过	未通过
代码语言	C++	运行时间	0.635 s
提交时间	2011-07-23 14:45:47	内存使用	4.13 MiB

#include <fstream>
#include <climits>

#define I_F "ping.in"
#define O_F "ping.out"
#define MAXn 1000
#define MAXq 100000
#define P 595000

using namespace std;

int n,t;
int map[MAXn][MAXn]={{0}};
bool f[MAXn]={false};
int ans=INT_MAX;
long p=0;

void Input();
void Dfs(int,int,short);
void Output();

int main()
{
	Input();
	Dfs(0,0,0);
	Output();
	return 0;
}

void Input()
{
	ifstream fin(I_F);
	int m,x,y;
	fin>>n>>m>>t;
	for (int i=0; i<m; i++)
	{
		fin>>x>>y;
		fin>>map[x][y];
		map[y][x]=map[x][y];
	}
	fin.close();
}

void Dfs(int s, int l, short d)
{
	p++;
	if (p<=P)
	{
		if (s==t)
		{
			if (l<ans)
				ans=l;
		}
		else
			if (d<10)
			{
				f[s]=true;
				for (int i=1; i<n; i++)
					if ((map[s][i]>0)&&(!f[i]))
						if (l+map[s][i]<ans)
							Dfs(i,l+map[s][i],d+1);
				f[s]=false;
			}
	}
}

void Output()
{
	ofstream fout(O_F);
	if (ans<INT_MAX)
		fout<<ans<<'\n';
	else
		fout<<"no\n";
	fout.close();
}