记录编号	37055	评测结果	AAAAAAAAAAAAAAAAA
题目名称	555.网络探测	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.127 s
提交时间	2012-03-23 08:25:51	内存使用	0.27 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int oo=~0u>>2;

struct edge
{
	int t,cost;
	edge *next;
	edge(int _t,int _cost,edge *_next):t(_t),cost(_cost),next(_next){}
}*Map[1001];

struct Node
{
	int tm,t,cost;
	Node(const int &_tm,const int &_t,const int &_cost):tm(_tm),t(_t),cost(_cost){}
	bool operator <(const Node &p)const{return cost>p.cost;}
};

int N,M,T,ans=oo;

inline void addedge(int s,int t,int cost)
{
	Map[s]=new edge(t,cost,Map[s]);
	Map[t]=new edge(s,cost,Map[t]);
}

void djs()
{
	priority_queue<Node>heap;
	bool flag[12][1001];
	int dist[12][1001];
	memset(flag,0,sizeof(flag));
	for(int i=0;i<12;i++)
		for(int j=1;j<=N;j++)
			dist[i][j]=oo;
	heap.push(Node(0,0,0));
	while(!heap.empty())
	{
		Node u=heap.top();
		heap.pop();
		if(u.tm>10||flag[u.tm][u.t])
			continue;
		dist[u.tm][u.t]=u.cost;
		flag[u.tm][u.t]=true;
		for(edge *p=Map[u.t];p;p=p->next)
		{
			int t=p->t,cost=p->cost;
			if(dist[u.tm][u.t]+cost<dist[u.tm+1][t])
			{
				dist[u.tm+1][t]=dist[u.tm][u.t]+cost;
				heap.push(Node(u.tm+1,t,dist[u.tm+1][t]));
			}
		}
	}
	for(int i=0;i<=10;i++)
		ans=min(ans,dist[i][T]);
	if(ans==oo)
		printf("no\n");
	else
		printf("%d\n",ans);
}

int main()
{
	freopen("ping.in","r",stdin);
	freopen("ping.out","w",stdout);
	scanf("%d%d%d",&N,&M,&T);
	for(int i=1;i<=M;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);
	}
	djs();
	return 0;
}