题目描述

　　每次有大的活动，大家都要在一起“聚一聚”，不管是去好乐迪，还是避风塘，或者汤姆熊，大家都要玩的痛快。还记得心语和花儿在跳舞机上的激情与释放，还记得草草的投篮技艺是如此的高超，还记得狗狗的枪法永远是'S'……还有不能忘了，胖子的歌声永远是让我们惊叫的！！ 　　今天是野猫的生日，所以想到这些也正常，只是因为是上学日，没法一起去玩了。但回忆一下那时的甜蜜总是一种幸福嘛。。。 　　但是每次集合的时候都会出现问题！野猫是公认的“路盲”，野猫自己心里也很清楚，每次都提前出门，但还是经常迟到，这点让大家很是无奈。后来，野猫在每次出门前，都会向花儿咨询一下路径，根据已知的路径中，总算能按时到了。 　　现在提出这样的一个问题：给出n个点的坐标，其中第一个为野猫的出发位置，最后一个为大家的集合位置，并给出哪些位置点是相连的。野猫从出发点到达集合点，总会挑一条最近的路走，如果野猫没找到最近的路，他就会走第二近的路。请帮野猫求一下这条第二最短路径长度。

输入格式

第一行是两个整数n(1<=n<=200)和m，表示一共有n个点和m条路，以下n行每行两个数xi，yi，(-500<=xi,yi<=500),代表第i个点的坐标，再往下的m行每行两个整数pj，qj,(1<=pj,qj<=n)，表示两个点相通。

输出格式

只有一行包含一个数，为第二最短路线的距离（保留两位小数），如果存在多条第一短路径，则答案就是第一最短路径的长度；如果不存在第二最短路径，输出－1。

样例输入

3 3 0 0 1 1 0 2 1 2 1 3 2 3

样例输出

2.83

题目分析

裸的次短路，注意double处理。

次短路在最短路的邻集中，断掉最短路上的边不断地dijkstra即可

源代码

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=205; //数组范围 struct Edge { //前向星 int from,to; double dist; bool vst; }; struct HeapNode { double d; int u; //u为当前结点 bool operator < (HeapNode a) const { return d>a.d; } }; struct Second_Dijkstra { //次短路 int n,m; vector<Edge> edges; //邻接表 vector<int> G[maxn]; //记录每个结点可以到达的结点 bool vst[maxn]; double dist[maxn]; int path[maxn],pathe[maxn]; //使用path记录最短路 void init(int n) { this->n=n; for(int i=1; i<=n; i++)G[i].clear(); edges.clear(); } void AddEdge(int from,int to,double dist) { edges.push_back((Edge) { from,to,dist,0 }); m=edges.size(); G[from].push_back(m-1); } void dijkstra(int s) { //核心算法 priority_queue<HeapNode> Q; for(int i=1; i<=n; i++)dist[i]=1e10; dist[s]=0; path[s]=s; memset(vst,0,sizeof(vst)); Q.push((HeapNode) { 0,s }); while(!Q.empty()) { HeapNode Now=Q.top(); Q.pop(); if(vst[Now.u])continue; vst[Now.u]=1; for(int i=0; i<G[Now.u].size(); i++) { Edge& e=edges[G[Now.u][i]]; //边的信息 int Next=e.to; if(e.vst)continue; if(dist[Next]>dist[Now.u]+e.dist) { dist[Next]=dist[Now.u]+e.dist; path[Next]=Now.u; pathe[Next]=G[Now.u][i]; Q.push((HeapNode) { dist[Next],Next }); } } } } double main(int s,int t) { dijkstra(s); int Path[maxn],Pathe[maxn]; double ans=1e10; memcpy(Path,path,sizeof(path)); memcpy(Pathe,pathe,sizeof(pathe)); for(int i=t; i!=s; i=Path[i]) { Edge& e=edges[Pathe[i]]; e.vst=1; edges[Pathe[i]^1].vst=1; dijkstra(s); ans=min(ans,dist[t]); e.vst=0; edges[Pathe[i]^1].vst=0; } return ans; } void Output(int x) { if(path[x]==x) { cout<<x<<" "; return; } Output(path[x]); cout<<x<<" "; } } ; Second_Dijkstra dij; int n,m; struct Point { double x,y; } a[205]; double Dist(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int main() { ios::sync_with_stdio(false); cin>>n>>m; dij.init(n); for(int i=1; i<=n; i++)cin>>a[i].x>>a[i].y; for(int i=1; i<=m; i++) { int x,y; cin>>x>>y; dij.AddEdge(x,y,Dist(a[x],a[y])); dij.AddEdge(y,x,Dist(a[x],a[y])); } printf("%0.2lf",dij.main(1,n)); return 0; }