【Educational Codeforces Round 40】D - Fight Against Traffic （最短路，disjkstra）

【Educational Codeforces Round 40】D - Fight Against Traffic （最短路，disjkstra）

题意： 给n个点，m条边，起点s，重点t，保证s到t的最短路径不变的情况下，求加一条边的方案数 分析： 看了半天题意， 才看明白说的是什么。 通过disjkstra求s和t到其他点的最短距离，然后如果两个点之间的距离之和+1不小于s到t的距离，方案数+1，具体表达见代码 #include using namespace std; #define mem(a,n) memset(a,n,sizeof(a)) #define memc(a,b) memcpy(a,b,sizeof(b)) #define rep(i,a,n) for(int i=a;i=a;i--)///[n,a] #define pb push_back #define fi first #define se second #define IO ios::sync_with_stdio(false) #define fre freopen("in.txt","r",stdin) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 typedef long long ll; typedef unsigned long long ull; const double PI=acos(-1.0); const double E=2.718281828459045; const double eps=1e-3; const int INF=0x3f3f3f3f; const int MOD=1e8+7; const int N=1e3+5; const ll maxn=1e6+5; const int dir[4][2]= {-1,0,1,0,0,-1,0,1}; struct Node { int v,w; Node() {} Node(int v,int w=1):v(v),w(w) {} }; int n,m,s,t; vectorg[N]; int ds[N],dt[N];///ds表示从s到其他点的距离，dt表示从t到其他点的距离 bool linked[N][N],vis[N]; void bfs(int src,int dis[]) { mem(vis,0); queueque; que.push(src); vis[src]=1; dis[src]=0; while(!que.empty()) { int u=que.front(); que.pop(); for(auto x: g[u]) { int v=x.v; if(vis[v]) continue; vis[v]=1; dis[v]=dis[u]+x.w; que.push(v); } } } void solve() { int dist=dt[s],ans=0; //cout<=dist&&ds[j]+dt[i]+1>=dist)///如分析 ans++; //cout<<"ans="<>n>>m>>s>>t) { mem(linked,0); rep(i,0,n+1) g[i].clear(); while(m--) { int u,v; cin>>u>>v; linked[u][v]=linked[v][u]=1; g[u].pb({v,1}); g[v].pb({u,1}); } bfs(s,ds); bfs(t,dt); solve(); } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。