首页 > 代码库 > CSU 1307 最短路+二分

CSU 1307 最短路+二分

2024-07-17 15:12:35   219人阅读

题目大意：

帮忙找到一条a到b的最短路，前提是要保证路上经过的站点的最大距离尽可能短

 

这道题居然要用到二分。。。完全没去想过，现在想想求最大距离的最小值确实是。。。

这里不断二分出值代入spfa（）或者dijkstla（）中计算a到b的最短距离，每次都保证只经过边小于mid值的路径

 1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 #define N 2005 8 #define LL long long 9 int first[N],k,visit[N];10 int dp[N];11 struct Path{12     int x,y,next,d;13 }path[100005];14 void add(int x,int y,int d)15 {16     path[k].y=y,path[k].d=d,path[k].next=first[x];17     first[x]=k;18     k++;19 }20 bool spfa(int u,int b,int mid)21 {22     queue<int> q;23     memset(dp,-1,sizeof(dp));24     memset(visit,0,sizeof(visit));25     dp[u]=0,visit[u]=1;26     q.push(u);27     while(!q.empty()){28         int v=q.front();29         q.pop();30         visit[v]=0;31         for(int i=first[v];i!=-1;i=path[i].next){32             int t=path[i].y;33             if(path[i].d<=mid&&(dp[t]>dp[v]+path[i].d||dp[t]<0)){34                 dp[t]=dp[v]+path[i].d;35                 if(!visit[t]) visit[t]=1,q.push(t);36             }37         }38     }39     return dp[b]!=-1;40 }41 int main()42 {43     int n,m,a,b,u,v,w;44     while(scanf("%d%d%d%d",&n,&m,&a,&b)!=EOF){45         memset(first,-1,sizeof(first));46         k=0;47         for(int i=0;i<m;i++){48             scanf("%d%d%d",&u,&v,&w);49             add(u,v,w);50             add(v,u,w);51         }52         int st=0,la=10000,mid,ans;53         while(st<=la){54             mid=(st+la)/2;55             if(spfa(a,b,mid)) ans=dp[b],la=mid-1;56             else st=mid+1;57         }58         printf("%d\n",ans);59     }60     return 0;61 }

 


联系
我们