CodeForces - 954D Fight Against Traffic(最短路，dijkstra)

本文主要是介绍CodeForces - 954D Fight Against Traffic(最短路，dijkstra)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

Little town Nsk consists of n junctions connected by m bidirectional
roads. Each road connects two distinct junctions and no two roads
connect the same pair of junctions. It is possible to get from any
junction to any other junction by these roads. The distance between
two junctions is equal to the minimum possible number of roads on a
path between them.

In order to improve the transportation system, the city council asks
mayor to build one new road. The problem is that the mayor has just
bought a wonderful new car and he really enjoys a ride from his home,
located near junction s to work located near junction t. Thus, he
wants to build a new road in such a way that the distance between
these two junctions won’t decrease.

You are assigned a task to compute the number of pairs of junctions
that are not connected by the road, such that if the new road between
these two junctions is built the distance between s and t won’t
decrease.

Input

The firt line of the input contains integers n, m, s and t
(2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000, 1 ≤ s, t ≤ n, s ≠ t) — the number of
junctions and the number of roads in Nsk, as well as the indices of
junctions where mayors home and work are located respectively. The
i-th of the following m lines contains two integers ui and vi
(1 ≤ ui, vi ≤ n, ui ≠ vi), meaning that this road connects junctions
ui and vi directly. It is guaranteed that there is a path between any
two junctions and no two roads connect the same pair of junctions.

Output

Print one integer — the number of pairs of junctions not connected by
a direct road, such that building a road between these two junctions
won’t decrease the distance between junctions s and t.

input

output

input

output

input

output

思路

这道题给了n个点和m条边，还给了一个起点和终点，问最多加多少条边，可以使得起点到终点的最短路不会变小。

首先我们可以知道，在有n个点的图中，最多有 $\frac{n(n-1)}{2}$ 条边，我们可以首先从起点和终点分别跑一下最短路，运用dijkstra算法，假设从起点开始的最短路是dis1[]数组，从终点开始的是dis2[]数组，那么我们可以枚举一下图中没有出现过的边，然后判断是否满足条件:
dis1[i]+1+dis2[j]>=dis1[ed]且dis2[i]+1+dis1[j]>=dis2[st]就证明这一条边的加入不会影响从起点到终点的最短路，那么就证明这一条边可以加入

代码

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
const int N=1000+20;
int e[N][N];
int n,m;
void init()
{for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)e[i][j]=i==j?0:inf;
}
struct Dijkstra
{int vis[N],dis[N];void dijkstra(int st){for(int i=1; i<=n; i++){dis[i]=inf;vis[i]=0;}dis[st]=0;for(int i=1; i<=n; i++){int minn=inf,k;for(int j=1; j<=n; j++)if(!vis[j]&&dis[j]<minn){minn=dis[j];k=j;}vis[k]=1;for(int j=1; j<=n; j++)if(!vis[j]&&dis[k]+e[k][j]<dis[j])dis[j]=dis[k]+e[k][j];}}
} ac1,ac2;
int main()
{int u,v,st,ed;scanf("%d%d%d%d",&n,&m,&st,&ed);init();for(int i=1; i<=m; i++){scanf("%d%d",&u,&v);e[u][v]=e[v][u]=1;}ac1.dijkstra(st);ac2.dijkstra(ed);int ans=0;for(int i=1; i<=n; i++)for(int j=i+1; j<=n; j++)if(e[i][j]==inf)if(ac1.dis[i]+1+ac2.dis[j]>=ac1.dis[ed]&&ac2.dis[i]+1+ac1.dis[j]>=ac2.dis[st])ans++;printf("%d\n",ans);return 0;
}