记录编号	61525	评测结果	AAAAAAAAAAAAAAAAA
题目名称	网络探测	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2013-06-11 19:13:09	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int SIZEN=1010,INF=0x7fffffff;
vector<pair<int,int> > c[SIZEN];
priority_queue<pair<int,int> > Q;
int N,M;
int past[SIZEN]={0};
void SPFA(int S,int T){
	queue<int> Q;
	int inq[SIZEN]={0};
	int f[SIZEN]={0};
	int i,u,v;
	for(i=0;i<=N;i++) inq[i]=false,f[i]=INF,past[i]=INF;
	past[S]=0,f[S]=0,inq[S]=true,Q.push(S);
	while(!Q.empty()){
		u=Q.front();Q.pop();
		inq[u]=false;
		if(past[u]>=10) continue;
		for(i=0;i<c[u].size();i++){
			v=c[u][i].first;
			if(f[v]>f[u]+c[u][i].second){
				f[v]=f[u]+c[u][i].second;
				past[v]=past[u]+1;
				if(!inq[v]){
					inq[v]=true;
					Q.push(v);
				}
			}
		}
	}
	if(f[T]==INF) cout<<"no"<<endl;
	else cout<<f[T]<<endl;
}
int main(){
	freopen("ping.in","r",stdin);
	freopen("ping.out","w",stdout);
	int T;
	scanf("%d%d%d",&N,&M,&T);
	int i,a,b,w;
	for(i=1;i<=M;i++){
		scanf("%d%d%d",&a,&b,&w);
		c[a].push_back(make_pair(b,w));
		c[b].push_back(make_pair(a,w));
	}
	SPFA(0,T);
	return 0;
}