題目大意：
給出n個點和m條道路，接下來有m行，每行輸入每條道路的起點和終點，權值均為1，在這座城市有個奇怪的特性：人們總是會走最短的路，你的任務是在1 - n中找出一個點設定為警局，我們規定：與警局相連的道路是安全的，即:5号是警局，那麼4 5 和5 6 都是安全的，每個警局對應兩條安全的道路（除了1和n）詢問所有安全道路中，平均安全道路的條數最多是多少。
解題思路：
跑一遍spfa計算dis[n]的最短距離和最短路的總條數，然後枚舉2 - （n - 1）個點，每個點跑spfa，如果dis【1】 + dis【n】 = 最短距離，那麼ans = max
（ans，平均距離），關于dp計數，路徑條數 = dp[1] · dp[n] · 2,dp為起點到i點的道路數，枚舉即可。
Code：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int mod = 1e9 + 7;
const int N = 550;
const int inf = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, double> pid;
bool vis[N];
int dis[N], n, m, len;
ll dp[N];//注意一下開long long
vector<int > e[N];//鄰接表存圖
void spfa(int s)
{
for (int i = 1; i <= n; i ++)
dis[i] = inf;
memset(vis, 0, sizeof vis);
memset(dp, 0, sizeof dp);
dis[s] = 0, dp[s] = 1;
queue<int > q;
q.push(s);
vis[s] = true;
while(!q.empty())
{
int now = q.front();
q.pop(), vis[now] = false;
for (int i = 0; i < e[now].size(); i++)
{
int k = e[now][i];
if (dis[now] + 1 < dis[k])
{
dis[k] = dis[now] + 1;
dp[k] = dp[now];
if (!vis[k])
{
vis[k] = true;
q.push(k);
}
}
else if (dis[now] + 1 == dis[k])
dp[k] += dp[now];
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i ++)
{
int a, b;
cin >> a >> b;
e[a].push_back(b);
e[b].push_back(a);
}
double ans = 1.0;
spfa(1);
len = dis[n];
double all = dp[n];
for (int i = 2; i <= n - 1; i ++)
{
spfa(i);
if (dis[1] + dis[n] == len)
ans = max(ans, (dp[1] * dp[n] * 2.0) / (double)all);
}
//cout << all << endl;
printf("%.12lf\n", ans);
return 0;
}