记录编号	522071	评测结果	AAAAAAAAAA
题目名称	[Tyvj Feb11] GF打dota	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.199 s
提交时间	2018-11-08 21:44:30	内存使用	4.55 MiB

#include<bits/stdc++.h>
using namespace std;
const int INF=999999;
int dis1[10010],dis2[10010],d[10010];
int m,n,k,l,p;
struct node
{ int to,len;
};
queue<int> que;
struct point
{ int u,v,w;
}a[50010];
vector<node> g[50010];
bool inque[10010];
void SPFA(int s)
{ memset(inque,0,sizeof(inque));
  memset(d,INF,sizeof(d));
  inque[s]=true;que.push(s);d[s]=0;
  while(!que.empty())
  { int u=que.front();
    inque[u]=false;que.pop();
    for (int i=0;i<g[u].size();i++)
    { int v=g[u][i].to;
      int w=g[u][i].len;
      if (d[u]+w<d[v]) {d[v]=d[u]+w;
	                   if (!inque[v])
					   { inque[v]=true;
					     que.push(v);}
						}
	}
  }
}
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 x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    g[x].push_back((node){y,z});
	g[y].push_back((node){x,z});
	a[i].u=x;a[i].v=y;a[i].w=z;
  }
  scanf("%d",&p);
  SPFA(1);
  int tx=d[n];
  if (p==0) {printf("%d",d[n]);return 0;}
  for (int i=1;i<=n;i++)
  dis1[i]=d[i];
  SPFA(n);
  for (int i=1;i<=n;i++)
  dis2[i]=d[i];
  int ans=INF;
  for (int i=1;i<=m;i++)
  { if (dis1[a[i].u]+dis2[a[i].v]+a[i].w<ans&&dis1[a[i].u]+dis2[a[i].v]+a[i].w!=tx)
    ans=dis1[a[i].u]+dis2[a[i].v]+a[i].w;  
    if (dis1[a[i].v]+dis2[a[i].u]+a[i].w<ans&&dis1[a[i].v]+dis2[a[i].u]+a[i].w!=tx)
    ans=dis1[a[i].v]+dis2[a[i].u]+a[i].w;
  }
  printf("%d",ans);
  return 0; 
}