首页 > 代码库 > SCU 4444 Travel
SCU 4444 Travel
$BFS$。
如果$1$和$n$之间存在一条长度为$b$的边，那么还需要去计算只走长度为$a$的边的最小时间。
如果$1$和$n$之间存在一条长度为$a$的边，那么还需要去计算只走长度为$b$的边的最小时间。
第一种情况直接$BFS$即可。
第二种情况需要反过来思考，因为补图的边太多了，对于$BFS$某一层的点，如果当前已经确定最短路径的点的个数大于与它直接相连的确定最短路径的点的个数，那么这个点也可以确定最短路径了。
#include <bits/stdc++.h>using namespace std;int n,m;long long a,b;int h[200010];int nx[500010*2],to[500010*2];long long dis[200010];long long INF = 1e18;int sz;void add(int A,int B){ to[sz]=B; nx[sz] = h[A]; h[A]=sz++;}void xiang578(){ queue<int>Q; for(int i=1;i<=n;i++) dis[i] = INF; dis[1]=0; Q.push(1); while(!Q.empty()) { int t = Q.front(); Q.pop(); for(int i=h[t];i!=-1;i=nx[i]) { if(dis[t]+a<dis[to[i]]) { dis[to[i]] = dis[t]+a; Q.push(to[i]); } } }}void work(){ queue<int>Q[2]; int now=n; for(int i=1;i<=n;i++) dis[i] = b; dis[1]=0; for(int i = h[1];i!=-1;i=nx[i]) { Q[0].push(to[i]); dis[to[i]]=INF; now--; } int k=0; for(int c=2;;c++) { int ff=0; while(!Q[k].empty()) { int t=Q[k].front();Q[k].pop(); int sum=0; for(int i=h[t];i!=-1;i=nx[i]) { if(dis[to[i]]<c*b) sum++; } if(sum==now) Q[k^1].push(t); else { dis[t] = c*b; ff++; } } k=k^1; now=now+ff; if(ff==0) break; }}int main(){ while(~scanf("%d%d%lld%lld",&n,&m,&a,&b)) { memset(h,-1,sizeof h); sz=0; int f=0; for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); if(u==1&&v==n) f=1; if(v==1&&u==n) f=1; } if(f==0) { xiang578(); printf("%lld\n",min(b,dis[n])); } else { work(); printf("%lld\n",min(a,dis[n])); } } return 0;}
SCU 4444 Travel
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。