Description
贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路，每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1，她的朋友们居住在农场N（即贝茜每次旅行的目的地）。 贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。
刷水有利于健康。
话说这还是前天考试的T3嘞。。。
code：
#include <iostream>#include <cstdio>#include <queue>using namespace std;const int wx=200017;inline int read(){ int sum=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();} return sum*f;}int n,m,num,tot;int head[wx],diss[wx],dist[wx],vis[wx];struct e{ int nxt,to,dis;}edge[wx*2];void add(int from,int to,int dis){ edge[++num].nxt=head[from]; edge[num].to=to; edge[num].dis=dis; head[from]=num;}struct node{ int u,d; friend bool operator < (const node & a,const node &b){ return a.d>b.d; }};priority_queue<node >q;void Dijs(){ for(int i=1;i<=n;i++)diss[i]=0x3f3f3f3f,vis[i]=0; diss[1]=0; q.push((node){1,0}); while(q.size()){ int u=q.top().u; q.pop(); if(vis[u])continue; vis[u]=1; for(int i=head[u];i;i=edge[i].nxt){ int v=edge[i].to; if(diss[v]>diss[u]+edge[i].dis){ diss[v]=diss[u]+edge[i].dis; q.push((node){v,diss[v]}); } } }}void Dijt(){ for(int i=1;i<=n;i++)dist[i]=0x3f3f3f3f,vis[i]=0; dist[n]=0; q.push((node){n,0}); while(q.size()){ int u=q.top().u; q.pop(); if(vis[u])continue; vis[u]=1; for(int i=head[u];i;i=edge[i].nxt){ int v=edge[i].to; if(dist[v]>dist[u]+edge[i].dis){ dist[v]=dist[u]+edge[i].dis; q.push((node){v,dist[v]}); } } }}void work(){ int tmp=0x3f3f3f3f; int minn=diss[n]; for(int u=1;u<=n;u++){ for(int i=head[u];i;i=edge[i].nxt){ int v=edge[i].to; int now=diss[u]+dist[v]+edge[i].dis; if(now<tmp&&now>minn){ tmp=now; } } } printf("%d\n",tmp);}int main(){ n=read(); m=read(); for(int i=1;i<=m;i++){ int x,y,z; x=read(); y=read(); z=read(); add(x,y,z); add(y,x,z); } Dijs(); Dijt(); work(); return 0;}
