用来解决边长只有0，1或者可以抽象成只有0，1的最短路问题
由于图中的所有边长度不是0就是1，并且当我们走边长为0的边时不会增大路径的长度，所以我们想到了优先去走边长为0的边。
具体来说，我们优先用边长为0的边去更新其到达的节点的dist（最短路径），这样我们就保证了此时该节点的dist一定是最小的，你想想呀，我们之前一直用边长为0的点去更新，如果能更新到它，那么它就是由一个或多个边长为0的边与源点连接起来的，若更新不到，那么它最多经过这么多边长为0的边，剩下的就要走边长为1的点了，这样一次访问之后该节点的dist就确定了。
下面是双端队列的使用样式：
#include<iostream> #include<queue> #include<cstdio> #include<cmath> using namespace std; deque<int> q; int main() { int ans=0; q.push_front(1); q.push_back(2); q.push_back(3); while(!q.empty()) { cout<<q.front()<<endl; q.pop_front(); } return 0; }例题：Telephone Lines 在郊区有N座通信基站，P条双向电缆，第i条电缆连接基站Ai和Bi。特别地，1号基站是通信公司的总站，N号基站位于一座农场中。现在，农场主希望对通信线路进行升级，其中升级第i条电缆需要花费Li。 电话公司正在举行优惠活动。农场主可以指定一条从1号基站到N号基站的路径，并指定路径上不超过K条电缆，由电话公司免费提供升级服务。农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。求至少用多少钱能完成升级。 0=<K<N<=1000,1=<P<=10000。
“简单来说，本题是在无向图上求出一条从1到N的路径，使路径上第K+1大边权尽量小。”------摘自《算法竞赛进阶指南》 by lyd
具体做法：本题我们采用二分答案的做法，为什么呢，因为支付的钱更多时，可以实行的方案一定包含了支付的钱更少的方案，因此，答案具有单调性。重点在我们的check，我们可以把升级价格大于mid的电缆抽象成长度为1的边，把升级价格小于等于mid的电缆抽象成长度为0的边，然后求1到N的最短路即可，不超过K的话，就是合法方案，反之，亦反。
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<cstring> #define maxn 1005 using namespace std; int net[maxn*10],head[maxn*10],ver[maxn*10]; bool vis[maxn]; int w[maxn],dist[maxn]; int n,p,k; int tot; deque<int> q;//双端队列 void add(int x,int y) { ver[++tot]=y; net[tot]=head[x]; head[x]=tot; } bool check(int mid) { while(!q.empty())//每次检查都把双端队列清空 { q.pop_front(); } memset(dist,0x3f,sizeof(dist)); if(w[1]<=mid)//1号点也要判断 dist[1]=0; else dist[1]=1; memset(vis,false,sizeof(vis));//每次都要初始化 ，因为你要检查好多次 q.push_front(1); vis[1]=true; while(!q.empty()) { int p=0; int node=q.front();//取队头的节点 q.pop_front();//弹出队头的节点 for(int i=head[node];i;i=net[i]) { int edge;//判断价格是否大于mid if(w[ver[i]]>mid) edge=1;//大于，边长就是1 else edge=0;//小于等于，边长就是0 if(dist[ver[i]]>dist[node]+edge) dist[ver[i]]=dist[node]+edge; if(ver[i]==n)//第一次更新到n之后就是最小值了，因此就可以结束了 { p=1; break; } if(!edge) q.push_front(ver[i]);//边长是0，加入到队头 else q.push_back(ver[i]); //边长是1，加入到队尾 } if(p==1) break; } if(dist[n]>k) return false;//1到n的最短路如果大于K，该方案就不合理 return true;//否则，合理 } int main() { scanf("%d%d%d",&n,&p,&k); for(int i=1;i<=p;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); } int mmax=-1; for(int i=1;i<=n;i++) scanf("%d",&w[i]),mmax=max(mmax,w[i]); int l=0,r=mmax; while(l<=r)//二分的一种写法，还有其他的 { int mid=(l+r)/2; if(check(mid)) r=mid-1; else l=mid+1; } printf("%d",l); return 0; }由于没有数据，emmm，不保证代码的正确性，大家看看思路就行了。
有巨佬的话可以帮我改一下，谢谢。
