记录编号	423584	评测结果	AAAAAAAAAA
题目名称	[Tyvj Feb11] GF打dota	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.096 s
提交时间	2017-07-12 09:48:16	内存使用	8.89 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e5+10;
struct edge{int f,t,l;}w[N];
int n,m,p,head[N],next[N];
void add(int f,int t,int l){
	static int cnt=0;
	w[++cnt]=(edge){f,t,l};
	next[cnt]=head[f];
	head[f]=cnt;
}
typedef long long ll;
ll dis[N],disS[N],disT[N];
struct sit{
	int p;ll d;
	sit(int P=0){p=P;d=dis[p];}
	bool operator > (const sit &a)const{return d>a.d;}
};
priority_queue<sit,vector<sit>,greater<sit> > Q;
bool vis[N];
void dijsktra(int S){
	for (int i=1;i<=n;i++) dis[i]=1e16,vis[i]=0;
	dis[S]=0;Q.push(sit(S));
	while (!Q.empty()){
		int v=Q.top().p;Q.pop();
		if (vis[v]) continue;
		vis[v]=1;
		for (int i=head[v];i;i=next[i])
		if (dis[w[i].t]>dis[v]+w[i].l)
			dis[w[i].t]=dis[v]+w[i].l,Q.push(sit(w[i].t));
	}
}
int main()
{
	freopen("dota.in","r",stdin);
	freopen("dota.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		int u,v,l;
		scanf("%d%d%d",&u,&v,&l);
		add(u,v,l);add(v,u,l);
	}
	scanf("%d",&p);
	dijsktra(1);
	if (!p) return printf("%lld\n",dis[n]),0;
	for (int i=1;i<=n;i++) disS[i]=dis[i];
	dijsktra(n);
	for (int i=1;i<=n;i++) disT[i]=dis[i];
	ll Min=disS[n],ans=1e16;
	for (int i=1;i<=m*2;i++){
		ll now=disS[w[i].f]+disT[w[i].t]+w[i].l;
		if (now>Min) ans=min(ans,now);
	}
	printf("%lld\n",ans);
	return 0;
}