Travel SCU - 4444

本文主要是介绍Travel SCU - 4444，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.scu.edu.cn/soj/problem.action?id=4444

先看 1与n之间是否有原图边 有的话就求补图最短路和a比较 没有就求原图最短路和b比较 都是一边BFS

#include <bits/stdc++.h>
using namespace std;
#define ll long longstruct node
{int v;int next;
};queue <int> que0,que1,que2,que3,que4;
node edge[1000010];
ll dis[200010];
ll a,b;
int first[200010],book[200010],cnt[200010];
int n,m,num;void addedge(int u,int v)
{edge[num].v=v;edge[num].next=first[u];first[u]=num++;
}ll solveI()
{int i,u,v;while(!que0.empty()) que0.pop();memset(dis,0x3f,sizeof(dis));memset(book,0,sizeof(book));que0.push(1);dis[1]=0;book[1]=1;while(!que0.empty()){u=que0.front();que0.pop();for(i=first[u];i!=-1;i=edge[i].next){v=edge[i].v;if(!book[v]){que0.push(v);dis[v]=dis[u]+a;book[v]=1;}}}return dis[n];
}ll solveII()
{int i,u,v,sz,cur;while(!que1.empty()) que1.pop();while(!que2.empty()) que2.pop();while(!que3.empty()) que3.pop();while(!que4.empty()) que4.pop();memset(dis,0x3f,sizeof(dis));memset(book,0,sizeof(book));memset(cnt,0,sizeof(cnt));que1.push(1);for(i=2;i<=n;i++) que2.push(i);dis[1]=0;cur=1;while(!que1.empty()&&!que2.empty()){sz=que1.size();while(!que1.empty()){u=que1.front();que1.pop();for(i=first[u];i!=-1;i=edge[i].next){v=edge[i].v;if(book[v]!=cur) cnt[v]=1;else cnt[v]++;book[v]=cur;}}while(!que2.empty()){u=que2.front();que2.pop();if(book[u]!=cur||cnt[u]<sz){que3.push(u);dis[u]=cur*b;}else que4.push(u);}while(!que3.empty()){u=que3.front();que3.pop();que1.push(u);}while(!que4.empty()){u=que4.front();que4.pop();que2.push(u);}cur++;}return dis[n];
}int main()
{int i,u,v,flag;while(scanf("%d%d%lld%lld",&n,&m,&a,&b)!=EOF){memset(first,-1,sizeof(first));num=0,flag=0;for(i=1;i<=m;i++){scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);if((u==1&&v==n)||(u==n&&v==1)) flag=1;}if(!flag) printf("%lld\n",min(b,solveI()));else printf("%lld\n",min(a,solveII()));}return 0;
}

 

这篇关于Travel SCU - 4444的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---