记录编号	25998	评测结果	AAAAAAAAAAAAAAAAA
题目名称	网络探测	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.075 s
提交时间	2011-07-22 15:46:07	内存使用	11.88 MiB

#include <cstdio>
#include <queue>
using namespace std;

#define pb push_back
#define mp make_pair
typedef pair<int,pair<int,int> > Pair;
const int MAXN=1005;
const int oo=~0u>>2;

struct Node
{
	int v,w;
	Node *next;
	Node(){}
	Node(int _v,int _w,Node *_next):
		v(_v),w(_w),next(_next){}
	void *operator new (size_t,void *p){return p;}
}*adj[MAXN],pool[MAXN*MAXN],*mem=pool;

inline void addedge(int u,int v,int w)
{
	adj[u]=new (mem++)Node(v,w,adj[u]);
	adj[v]=new (mem++)Node(u,w,adj[v]);
}

int S=0,T;
int dis[MAXN][11];
bool sure[MAXN][11];
int N,M;
priority_queue<Pair,vector<Pair>,greater<Pair> > q;
void dijkstra()
{
	for(int i=0;i<N;i++)
		for(int j=0;j<=10;j++)
			dis[i][j]=oo;
	dis[S][0]=0;
	q.push(mp(dis[S][0],mp(S,0)));
	while(q.size())
	{
		int u1,u2,nd;
		do
		{
			u1=q.top().second.first;
			u2=q.top().second.second;
			q.pop();
		}while(sure[u1][u2]);
		if (dis[u1][u2]==oo)
			break;
		if (u1==T)
		{
			printf("%d\n",dis[u1][u2]);
			return ;
		}
		if (u2==10)
			continue;
		sure[u1][u2]=true;
		for(Node *p=adj[u1];p;p=p->next)
			if (!sure[p->v][u2+1] && dis[p->v][u2+1]>(nd=dis[u1][u2]+p->w))
			{
				dis[p->v][u2+1]=nd;
				q.push(mp(nd,mp(p->v,u2+1)));
			}
	}
	printf("no\n");
}

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