题意：
给出一个图的所有边，每次从图中删除一条边，求任意点对的路径总和（求完了就将边给补回去）。（有重边）
思路：
#include <bits/stdc++.h>
using namespace std;
const int N=, INF=0x7f7f7f7f;
int mapp[N][N];
bool vis[N]; //是否存在队列中
int dest[N];
vector<pair<int,int> > vect;
int n, m;
int num[N]; void spfa(int x)
{
memset(vis,,sizeof(vis));
memset(dest,0x7f,sizeof(dest));
deque<int> que;
que.push_back(x);
vis[x]=;
dest[x]=;
while(!que.empty())
{
int tmp=que.front();
que.pop_front();
vis[tmp]=;
for(int i=; i<=n; i++)
{
if(mapp[tmp][i]> && dest[tmp]+<dest[i] )
{
dest[i]=dest[tmp]+;
if(!vis[i]) //没有在队列中
{
vis[i]=;
//que.push_back(i);
if(!que.empty() && dest[i]<dest[que.front()]) que.push_front(i);
else que.push_back(i);
}
}
}
}
} int cal()
{
int sum=;
for(int i=; i<=n; i++)
{ spfa(i);
for(int j=; j<=n; j++)
{
if(dest[j]==INF) return ;
sum+=dest[j];
}
}
return sum;
} int main()
{
freopen("input.txt", "r", stdin);
int a, b, c;
while(~scanf("%d%d", &n, &m))
{
vect.clear();
memset(mapp,,sizeof(mapp));
memset(num,,sizeof(num));
for(int i=; i<m; i++)
{
scanf("%d%d",&a,&b);
mapp[a][b]++;
mapp[b][a]++;
num[a]++;
num[b]++;
vect.push_back(make_pair(a,b));
} for(int i=; i<vect.size(); i++)
{
a=vect[i].first;
b=vect[i].second;
if(num[a]==||num[b]==)
{
printf("INF\n");
continue;
}
mapp[a][b]--; //先断开
mapp[b][a]--; int ans=cal();
if(ans==) printf("INF\n");
else printf("%d\n",ans); mapp[a][b]++; //再连上
mapp[b][a]++;
} } return ;
}
正确而TLE代码，spfa+暴力
#include <bits/stdc++.h>
using namespace std;
const int N=, INF=0x7f7f7f7f;
int mapp[N][N];//图矩阵
bool mapp2[N][N][N]; //标记从某点出发所需关键路径
int tem_sum[N];
int num[N]; //每个点的度
int vis[N]; //用于BFS
vector<pair<int,int> > vect; //m条边
int n, m; int bfs(int x)
{
memset(vis,,sizeof(vis));
deque<int> que(,x);
int cnt=, sum=;
vis[x]=;
while(!que.empty())
{
cnt++;
int siz=que.size();
for(int i=; i<siz; i++)
{
int tmp=que.front();
que.pop_front();
for(int j=; j<=n; j++)
{
if(!vis[j]&&mapp[tmp][j])
{
vis[j]=;
sum+=cnt;
mapp2[x][tmp][j]= mapp2[x][j][tmp]=;//主要在这，记录每个点出发所需要的关键路径
que.push_back(j);
}
}
}
}
return sum;
} int cal(int a,int b) //a-b是删除的边
{
int sum=;
for(int i=; i<=n; i++)
{
if(!a || mapp2[i][a][b] )
{
int tmp=bfs(i);
if(!tmp) return ;
if(!a) tem_sum[i]=tmp; //第一次求还得更新tem_sum
sum+=tmp;
}
else sum+=tem_sum[i];
}
return sum;
} int main()
{
//freopen("input.txt", "r", stdin);
int a, b, c;
while(cin>>n>>m)
{
vect.clear();
memset(mapp,,sizeof(mapp));
memset(mapp2,,sizeof(mapp2));
memset(num,,sizeof(num));
memset(tem_sum,,sizeof(tem_sum)); //一旦更新，不再改 for(int i=; i<m; i++)
{
scanf("%d%d",&a,&b);
mapp[a][b]++, mapp[b][a]++;
num[a]++, num[b]++;
vect.push_back(make_pair(a,b));
} int sum=cal(,); //先求sum，看能否每点互通，不通以下都不必计算了。
for(int i=; i<m; i++)
{
a=vect[i].first, b=vect[i].second;
if(num[a]== || num[b]== || m<n || sum== ) //度为1的点，边不够，不连通
{
printf("INF\n");
continue;
}
if(mapp[a][b]==) //仅有那么1条边，才需要更新
{
mapp[a][b]--, mapp[b][a]--; //先断开
int ans=cal(a,b);//只求需要该边的SSSP
if(ans==) printf("INF\n");
else printf("%d\n",ans);
mapp[a][b]++, mapp[b][a]++; //再连上
}
else printf("%d\n",sum); //非关键，直接输出
} }
return ;
}
AC代码(BFS)