题目链接： ，最短路(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#include #include #include #include #include #include #include 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 | 1const 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 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 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\n" , 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\n" , res); e[u][pos[u][i]].w = 1; //还原这条边 e[v][pos[v][i]].w = 1; } } } return 0;}