題面

完了，做的時候已經想不起來分層圖這個東西了QAQ

對于這種“多種”路徑加中轉站的題，還有那種有若干次“特殊能力”的題，都可以考慮用分層圖來做

顯然只需要記錄所有的中轉站+起點終點，然后拆出橫豎兩層，一層的點之間連值為$2$的邊，每個站的兩層之間連值為$1$的邊，然后再跑最短路。注意數組大小，還有起點和終點的兩層是連零邊的

1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=100005,inf=0x3f3f3f3f; 7 struct a 8 { 9 int xx,yy,id; 10 }mem[N]; 11 struct b{int node,dist;}; 12 bool operator < (b x,b y) 13 { 14 return x.dist>y.dist; 15 } 16 priority_queue<b> hp; 17 int val[6*N],dis[2*N],vis[2*N]; 18 int p[2*N],noww[6*N],goal[6*N]; 19 int n,m,t1,t2,st,ed,cnt,tot; 20 bool cmp1(a x,a y) 21 { 22 return x.xx==y.xx?x.yy<y.yy:x.xx<y.xx; 23 } 24 bool cmp2(a x,a y) 25 { 26 return x.yy==y.yy?x.xx<y.xx:x.yy<y.yy; 27 } 28 void link(int f,int t,int v) 29 { 30 noww[++cnt]=p[f],p[f]=cnt; 31 goal[cnt]=t,val[cnt]=v; 32 } 33 void Dijkstra(int s) 34 { 35 memset(dis,0x3f,sizeof dis); 36 dis[s]=0,hp.push((b){s,0}); 37 while(!hp.empty()) 38 { 39 b tt=hp.top(); hp.pop(); int tn=tt.node; 40 if(vis[tn]) continue ; vis[tn]=true; 41 for(int i=p[tn];i;i=noww[i]) 42 if(dis[goal[i]]>dis[tn]+val[i]) 43 dis[goal[i]]=dis[tn]+val[i],hp.push((b){goal[i],dis[goal[i]]}); 44 } 45 } 46 int main () 47 { 48 scanf("%d%d",&n,&m),st=++m,ed=++m; 49 link(st,st+m,0),link(st+m,st,0); 50 link(ed,ed+m,0),link(ed+m,ed,0); 51 for(int i=1;i<=ed;i++) 52 { 53 scanf("%d%d",&mem[i].xx,&mem[i].yy); 54 mem[i].id=++tot,link(tot,tot+m,1),link(tot+m,tot,1); 55 } 56 sort(mem+1,mem+1+tot,cmp1); 57 for(int i=1;i<=st;i++) 58 if(mem[i].xx==mem[i+1].xx) 59 { 60 link(mem[i].id,mem[i+1].id,2*(mem[i+1].yy-mem[i].yy)); 61 link(mem[i+1].id,mem[i].id,2*(mem[i+1].yy-mem[i].yy)); 62 } 63 sort(mem+1,mem+1+tot,cmp2); 64 for(int i=1;i<=st;i++) 65 if(mem[i].yy==mem[i+1].yy) 66 { 67 link(mem[i].id+m,mem[i+1].id+m,2*(mem[i+1].xx-mem[i].xx)); 68 link(mem[i+1].id+m,mem[i].id+m,2*(mem[i+1].xx-mem[i].xx)); 69 } 70 Dijkstra(st),dis[ed]>=inf?printf("-1"):printf("%d",dis[ed]); 71 return 0; 72 } View Code

?

轉載于:https://www.cnblogs.com/ydnhaha/p/9794974.html

總結

以上是生活随笔為你收集整理的解题：SHOI 2012 回家的路的全部內容，希望文章能夠幫你解決所遇到的問題。

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