---

問題描述

蒜頭君陷入了坐標系上的一個迷陣，迷陣上有 n 個點，編號從 1 到 n。蒜頭君在編號為 1 的位置，他想到編號為 n 的位置上。蒜頭君當然想盡快到達目的地，但是他覺得最短的路徑可能有風險，所以他會選擇第二短的路徑。現在蒜頭君知道了 n 個點的坐標，以及哪些點之間是相連的，他想知道第二短的路徑長度是多少。
注意，每條路徑上不能重復經過同一個點。
輸入格式
第一行輸入兩個整數 n (1≤n≤200) 和 m，表示一共有 n 個點和 m 條邊。
接下來輸入 n 行，每行輸入兩個整數xi,yi(?500≤xi,yi≤500)，代表第 ii 個點的坐標。
接下來輸入 mm 行，每行輸入兩個整數 pj,qj(1≤pj,qj≤n)，表示點pj和點 qj之間相連。
輸出格式
輸出一行，輸出包含一個數，表示第二短的路徑長度（小數點后面保留兩位），如果第一短路徑有多條，則答案就是第一最短路徑的長度；如果第二最短路徑不存在，則輸出 ?1。
樣例輸入
3 3
1 1
2 2
3 2
1 2
2 3
1 3
樣例輸出
2.41

---

AC代碼

原文傳送門

#include<iostream> #include<cstdio> #include<set> #include<vector> #include<cmath> #include<cstring> using namespace std; const int maxn=207; const int maxm=50007; //207*207 可能有重邊 所以再開大一些 不給數據范圍是真的睿智 int n,m; int x[maxn],y[maxn],fa[maxn],q[maxn]; double W(int u,int v); struct edge{ int v,nxt; double w; }e[maxm<<1]; //睿智了 打成了maxn int p[maxn],eid; double dist[maxn]; double ans=99999999; bool vst[maxn]; //int id[maxn][maxn]; typedef pair<double,int> pdi; set<pdi,less<pdi> >min_heap; void dijkstra(int a,int b); void ins(int u,int v); void ins2(int u,int v); void init(); int main(){ cin>>n>>m; init(); for(int i=1;i<=n;i++) cin>>x[i]>>y[i]; for(int i=1;i<=m;i++) { int a,b; cin>>a>>b; ins2(a,b); } int now=n; dijkstra(-1,-1); while(fa[now]){ dijkstra(fa[now],now); ans=min(dist[n],ans); now=fa[now]; } if(ans==99999999) printf("-1"); else printf("%.2lf",ans); return 0; } double W(int u,int v){return sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]));} void dijkstra(int a,int b){ memset(vst,false,sizeof(vst)); for(int i=1;i<=n;i++) dist[i]=99999999; dist[1]=0; min_heap.insert(make_pair(0,1)); for(int i=1;i<=n;i++){ if(min_heap.size()==0) break; auto iter=min_heap.begin(); int v=iter->second; min_heap.erase(*iter); if(vst[v]) continue; vst[v]=true; for(int j=p[v];j;j=e[j].nxt){ //枚舉相鄰邊 if(v==a&&e[j].v==b||v==b&&e[j].v==a) continue; //跳過最短路上的某條邊 int x=e[j].v; if(dist[x]>dist[v]+e[j].w){ min_heap.erase(make_pair(dist[x],x)); dist[x]=dist[v]+e[j].w; min_heap.insert(make_pair(dist[x],x)); if(a==-1&&b==-1) fa[x]=v; } } } } void ins(int u,int v){ e[++eid].v=v; e[eid].nxt=p[u]; e[eid].w=W(u,v); p[u]=eid; //eid要從1開始 0開始會炸 } void ins2(int u,int v){ins(u,v);ins(v,u);} //無向邊插兩次 void init(){ eid=0; memset(p,0,sizeof(p)); }

總結

以上是生活随笔為你收集整理的计蒜客习题：迷阵突围的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。