点这里
题意： 给定一个无向图，有n个点和m条边，每条边的权值均为1。要求每次只删除第i条边（分别删除m条边中的其中一条，求答案），求所有点之间的最短距离和，如果存在不连通的点则输出INF。 题解： 最多有三千条边，显然不可能分别删除，然后又分别去求所有点的最短距离，最后求和；也就是说这么做的话，我们可能需要运行3000*3000次Dijkstra。那么我们就要考虑什么样子的情况下，可以省去重复或者无用的计算。
重边： 看样例就知道是有可能存在重边的，那么在存在重边的情况下，我们删除重边的其中一条，是不会影响任意两点间的最短路径的。这条边本身就不属于任何最短路径： 比如u点到v点的最短路径为u->1->2->3->v根本不会经过4点，俺么删除关于4点的边就不会影响u到v的最短路径。所以我们需要记录所有节点的的最短路径，如果某条边不属于任何最短路径，那么我们只要放心删除就行了。
过程中犯的错：
TLE： 这题的难点就在于处理时间复杂度上，我有看过别人的题解，是可以用邻接表完成的，我有尝试过，但是始终找不出问题所在，反正就是一直TLE。最后改成了链式前向星存图。
#include<bits/stdc++.h>
using namespace std
;
const int N
= 105;
const int M
= 3005;
int n
, m
, u
, v
;
int dis
[N
], vis
[N
], sum
[N
];
int cnt
, head
[N
], G
[N
][N
];
int used
[N
][N
][N
];
struct edge
{ int v
, next
;} e
[2 * M
];
void addedge(int u
, int v
){
e
[cnt
].v
= v
, e
[cnt
].next
= head
[u
];
head
[u
] = cnt
++;
e
[cnt
].v
= u
, e
[cnt
].next
= head
[v
];
head
[v
] = cnt
++;
}
int bfs(int s
, int flag
){
for(int i
= 1; i
<= n
; i
++) dis
[i
] = vis
[i
] = 0;
queue
<int> q
;
q
.push(s
);
vis
[s
] = 1;
while(!q
.empty()){
int u
= q
.front(); q
.pop();
for(int i
= head
[u
]; ~i
; i
= e
[i
].next
){
int v
= e
[i
].v
;
if(vis
[v
] || !G
[u
][v
]) continue;
if(flag
) used
[s
][u
][v
] = used
[s
][v
][u
] = 1;
vis
[v
] = 1;
dis
[v
] = dis
[u
] + 1;
q
.push(v
);
}
}
int ans
= 0;
for(int i
= 1; i
<= n
; i
++){
if(i
== s
) continue;
if(!dis
[i
]) return -1;
ans
+= dis
[i
];
}
return ans
;
}
int main(){
while(~scanf("%d%d", &n
, &m
)){
cnt
= 0;
memset(G
, 0, sizeof G
);
memset(used
, 0, sizeof used
);
memset(head
, -1, sizeof head
);
for(int i
= 1; i
<= m
; i
++){
scanf("%d%d", &u
, &v
);
addedge(u
, v
);
G
[u
][v
]++, G
[v
][u
]++;
}
int ans
= 0, flag
= 1;
for(int i
= 1; i
<= n
&& flag
; i
++){
sum
[i
] = bfs(i
, 1);
if(sum
[i
] == -1) flag
= 0;
ans
+= sum
[i
];
}
for(int i
= 0; i
< m
; i
++){
u
= e
[(i
<< 1) ^ 1].v
, v
= e
[i
<< 1].v
;
G
[u
][v
]--, G
[v
][u
]--;
if(!flag
) printf("INF\n");
else if(G
[u
][v
]) printf("%d\n", ans
);
else{
int tem
= 0, tag
= 1;
for(int j
= 1; j
<= n
&& tag
; j
++){
if(used
[j
][u
][v
]){
int now
= bfs(j
, 0);
if(now
== -1) tag
= 0;
tem
+= now
;
}
else tem
+= sum
[j
];
}
if(!tag
) printf("INF\n");
else printf("%d\n", tem
);
}
G
[u
][v
]++, G
[v
][u
]++;
}
}
return 0;
}
