题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2433 ，最短路(SPFA或优化过的Dijstra) + 剪枝优化
这道题关键还是在几个剪枝上面，没有剪枝会TLE。
先说下几个数组的意义：
a[]存储M条边的信息；vis[i]表示点i是否访问过；path[i][u][v]表示在点i的所有最短路里，边u - v是否属于某条最短路；cnt[u][v]表示边u - v出现的次数；pos[u][i]表示第i条边在邻接表e[u]中的位置；sum[i]表示预处理时顶点i到所有顶点的最短路的和；dist[i]表示顶点i到其他顶点的最短路的距离；e[i]即邻接表，存储与顶点i邻接的点的信息。
算法：
先预处理一遍，求得每个顶点的最短路，并存在sum[i]中，如果预处理时发现图不连通，则M次询问都输出"INF"；
处理第i条边的时候，如果这条边出现不止一次，即 cnt[u][v] > 1，这时候除掉这条边后不影响结果，输出预处理的结果即可；
如果不满足上述条件，就开始求n个顶点的最短路情况：求顶点i的最短路的时候，如果边u - v不在顶点i的最短路中，即 path[i][u][v] == 0时，这时候这条边除掉不影响顶点i的最短路的结果，所以仍为sum[i]；如果出现去掉这条边图不连通的情况，这次询问输出"INF"。
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL __int64
#define eps 1e-8
#define INF 1e8
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int MOD = 2333333;
const int maxn = 100 + 5;
const int N = 3000 + 5;
struct Edge {
int v , w;
bool operator < (const Edge &tmp) const {
return w > tmp.w;
}
} a[N];
bool vis[maxn] , path[maxn][maxn][maxn];
int cnt[maxn][maxn] , pos[maxn][N];
int sum[maxn] , dist[maxn];
vector <Edge> e[maxn];
int Dijstra(int s , int n , bool ch) //Dijstra + 优先队列
{ //ch表示是否为预处理，因为在预处理的时候才需要判断path[i][u][v]的情况
memset(vis , 0 , sizeof(vis));
for(int i = 1 ; i <= n ; i++)
dist[i] = INF;
dist[s] = 0;
priority_queue <Edge> que;
Edge tmp = {s , 0};
que.push(tmp);
while(!que.empty()) {
Edge u = que.top();
que.pop();
if(vis[u.v])
continue;
vis[u.v] = 1;
for(int i = 0 ; i < e[u.v].size() ; i++) {
int j = e[u.v][i].v;
if(dist[j] > dist[u.v] + e[u.v][i].w) {
dist[j] = dist[u.v] + e[u.v][i].w;
if(!vis[j]) {
if(ch) //这条边在最短路中
path[s][u.v][j] = path[s][j][u.v] = 1;
que.push(e[u.v][i]);
}
}
}
}
int ans = 0;
for(int i = 1 ; i <= n ; i++) {
if(dist[i] >= INF)
return INF;
ans += dist[i];
}
return ans;
}
int main()
{
int n , m , u , v , i , ans;
while(~scanf("%d %d" , &n , &m))
{
memset(path , 0 , sizeof(path));
memset(cnt , 0 , sizeof(cnt));
for(i = 1 ; i <= n ; i++)
e[i].clear();
for(i = 1 ; i <= m ; i++) {
scanf("%d %d" , &u , &v);
Edge tmp = {v , 1};
e[u].push_back(tmp);
tmp.v = u;
e[v].push_back(tmp);
pos[u][i] = e[u].size() - 1;
pos[v][i] = e[v].size() - 1;
cnt[u][v]++;
cnt[v][u]++;
a[i].v = u;
a[i].w = v;
}
bool flag = false;
for(i = 1 , ans = 0 ; i <= n ; i++) {
sum[i] = Dijstra(i , n , 1);
if(sum[i] == INF) {
flag = true;
break;
}
ans += sum[i];
}
for(i = 1 ; i <= m ; i++) {
u = a[i].v;
v = a[i].w;
if(flag) {
puts("INF");
} else if(cnt[u][v] > 1) {
printf("%d
" , ans);
} else {
int tmp , res;
res = ans;
e[u][pos[u][i]].w = INF; //删掉第i条边
e[v][pos[v][i]].w = INF;
for(int j = 1 ; j <= n ; j++) {
if(path[j][u][v]) {
tmp = Dijstra(j , n , 0);
if(tmp == INF) {
puts("INF");
break;
}
res += tmp - sum[j];
}
}
if(tmp != INF)
printf("%d
" , res);
e[u][pos[u][i]].w = 1; //还原这条边
e[v][pos[v][i]].w = 1;
}
}
}
return 0;
}