给我们一张图，问我们摧毁边使得s和t不连通有多少种方案， 方案与方案之间不能存在相同的摧毁目标。
这是一个神奇的题目。
这题可以转为求s与t的最短路，为什么呢？
因为方案与方案之间不能存在相同的催婚目标。
那么最短路上的边肯定要被摧毁，才能使得s和t不连通。
那么只要一个方案摧毁最短路上的一条边，外加一些最短路外的边， 那么就会使得方案数最多。方案数为最短路的长度。
那么问题来了，我们摧毁的最短路上的边是不会相同的，但是最短路外的边呢？会不会相同呢？
我们假设最短路是s -- x1 -- x2 -- x3 -- x4--...---t
我们删除最短路的第一条边 s--x1, 删除后图可能还是连通的，因为s与x2,x3,x4...t可能还有间接的边。
s与x2的间接边长度长度至少为2，s与x2的间接边长度至少为3，依次类推。不然原来的最短路就不是最短路了
所以我们只要删除这些间接边的第一条边。
我们删除最短路的第二条边 x1--x2, 然后删除以x1开头，删除以s开头的连向x3,x4...t的间接边的第二条边
删除以x1开头的连向以x1开头，连向x3,x4,...t的间接边的第一条边，
以此类推。 摧毁最短路之外的边是不会相同的。
所以，我们求个s->t的最短路就行了
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = <<;
/* */
struct Edge
{
int to,dist;
bool operator<(const Edge&rhs)const
{
return dist > rhs.dist;
}
};
vector<Edge> g[+];
int dist[+];
bool vis[+];
void dij(int s)
{
priority_queue<Edge> q;
Edge cur,tmp;
cur.dist = ;
cur.to = s;
q.push(cur);
dist[s] = ;
while(!q.empty())
{
cur = q.top(); q.pop();
int u = cur.to;
if(vis[u]) continue;
vis[u] = true;
for(int i=; i<g[u].size(); ++i)
{
int v = g[u][i].to;
if(dist[v] > dist[u] + g[u][i].dist)
{
tmp.dist = dist[v] = dist[u] + g[u][i].dist;
tmp.to = v;
q.push(tmp);
}
}
} }
int main()
{
int n,m,s,t,i,a,b;
Edge tmp;
while(true)
{
scanf("%d%d%d%d",&n,&m,&s,&t);
if(n==)
break;
for(i=; i<=n; ++i)
{
g[i].clear();
vis[i] = false;
dist[i] = INF;
}
for(i=; i<m; ++i)
{
scanf("%d%d",&a,&b);
tmp.to = b;
tmp.dist = ;
g[a].push_back(tmp);
tmp.to = a;
g[b].push_back(tmp);
}
dij(s);
printf("%d\n",dist[t]);
}
return ;
}