关于 HDU 2433

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 105;
const int MAXM = 3005;
const int inf = 0x3f3f3f3f;
int n, m;
struct Edge {
    int to, idx;
    Edge (int _to = 0, int _idx = 0) :
        to(_to), idx(_idx) {}
};
vector<Edge> e[MAXN];
long long ans[MAXM] = {0};
int dis[MAXN] = {0};
bool vld[MAXM] = {false};
void bfs(int st) {
    memset(dis, 0x3f, sizeof dis);
    queue<int> q;
    q.push(st), dis[st] = 0;
    while (!q.empty()) {
        int h = q.front();
        q.pop();
        for (int id = 0; id < (int)e[h].size(); id++) {
            Edge i = e[h][id];
			if (!vld[i.idx] && dis[i.to] > dis[h] + 1) {
                dis[i.to] = dis[h] + 1;
                q.push(i.to);
            }
		}
    }
}
bool inTr[MAXM] = {false};
bool vis[MAXN] = {false};
bool f[MAXM] = {0};
void build(int st) {
    memset(inTr, false, sizeof inTr);
    memset(vis, false, sizeof vis);
    queue<int> q;
    q.push(st), vis[st] = true;
    while (!q.empty()) {
        int h = q.front();
        q.pop();
        for (int id = 0; id < (int)e[h].size(); id++) {
        	Edge i = e[h][id];
		    if (!vis[i.to] && dis[i.to] == dis[h] + 1) {
                inTr[i.idx] = vis[i.to] = true;
                q.push(i.to);
            }
    	}
    }
}
void slv(int x) {
    bfs(x);
    build(x);
    long long sum = 0;
    bool flg = false;
    for (int i = 1; i <= n; i++)
        if (dis[i] == inf) 
            flg = true;
        else
            sum += dis[i];
    for (int i = 1; i <= n; i++) {
        for (int id = 0; id < (int)e[i].size(); id++) {
        	Edge j = e[i][id]; 
            f[j.idx] = flg;
            if (inTr[j.idx]) {
                vld[j.idx] = true;
                bfs(x);
                vld[j.idx] = false;
                for (int k = 1; k <= n; k++)
                    if (dis[k] == inf)
                        f[j.idx] = true;
                    else
                        ans[j.idx] += dis[k];
            }
            else
                ans[j.idx] += sum;
        }
    }
}
int main() { 
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i++)
            ans[i] = 0, e[i].clear();
        for (int i = 1, u, v; i <= m; i++) {
            scanf("%d%d", &u, &v);
            e[u].push_back(Edge(v, i));
            e[v].push_back(Edge(u, i));
        }
        for (int i = 1; i <= n; i++)
            slv(i);
        for (int i = 1; i <= m; i++)
            if (f[i])
                printf("INF\n");
            else
                printf("%lld\n", ans[i] / 2);
    }
    return 0;
}