SPFA_queue_チェーンフロントスター最短路&HDU 2433

最短路spfa,sum配列は各点から各点までの最短路の和を記録し、ansを総和とし、その後、辺u-vを一つ一つ削除し、uに関する最短路を求め、dis[v]が無限大であれば、INFを出力し、そうでなければ連通--』sum【u】--新しい変数num 1で記録して上書きできないsumv=num 2を求め、出力+』ans-sum[u]-sum[v]+num 1+num 2を求める
チェーン式の前方星とspfa--queueの最短ルートの求め方を振り返った.
1・初期化開始点、エンキュー
2.1つのポイント(vis配列のメンテナンス)をキューし、このポイントを起点とするすべてのエッジ、エッジをスキャンします.
3.目標点がチームにあるかどうかを判断し、チームに入らない
キュー、vis配列、dis配列を常に維持

/*
sum      i         
ans  i 1 n   sum[i]  
    u v 
1.uv     
2. sum[u]
3.sum[v]
ans = ans - sum[u] - sum[v] + num1 + num2
*/

#include 
#include 
#include 
#include 
#define inf 99999999
using namespace std;
const int maxn = 110;
const int maxm = 3030;
typedef long long ll;


struct node{
    int from,to,pre;
    int cost;//     cost        inf    
}e[maxm * 2];

int n,m,ans;//        
int sum[maxn];//            
int dis[maxn];//spfa    —— i          
int vis[maxn];//spfa    ——   i      
int id[maxm],cnt;//     
int u[maxm],v[maxm];//    
queue q;
void init()
{
    //           
    memset(sum,0,sizeof(sum));
    memset(id,-1,sizeof(id));
    cnt = 0;
    ans = 0;
}

void add(int u,int v)
{
    e[cnt].from = u;
    e[cnt].to = v;
    e[cnt].cost = 1;
    e[cnt].pre = id[u];
    id[u] = cnt++;
}

int spfa(int s)
{
    for(int i = 0;i <= n;i++)
    {
        dis[i] = inf;
    }
    memset(vis,0,sizeof(vis));
    while(q.size())q.pop();

    q.push(s);
    dis[s] = 0;
    vis[s] = 1;
    while(q.size())
    {
        int now = q.front();
        q.pop();
        vis[now] = 0;
        for(int i = id[now];~i;i = e[i].pre)
        {
            int to = e[i].to;
            if(dis[to] > dis[now] + e[i].cost)
            {
                dis[to] = dis[now] + e[i].cost;
                if(vis[to] == 0)
                {
                    vis[to] = 1;
                    q.push(to);
                }
            }
        }
    }
    int res = 0;
    for(int i = 1;i <= n;i++)
        res += dis[i];
    return res;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();

        for(int i = 1;i <= m;i++)
        {
            scanf("%d%d",&u[i],&v[i]);
            add(u[i],v[i]);
            add(v[i],u[i]);
        }

        for(int i = 1;i <= n;i++)
        {
            sum[i] = spfa(i);
            ans += sum[i];
        }

        for(int i = 1;i <= m;i++)
        {
            e[i*2-1].cost = inf;
            e[i*2-2].cost = inf;
            int num1 = spfa(u[i]);
            if(dis[v[i]] >= inf)
                printf("INF
");
            else
            {
                int num2 = spfa(v[i]);
                printf("%d
",ans + num1 + num2 - sum[u[i]] - sum[v[i]]);
            }
            e[i*2-1].cost = 1;
            e[i*2-2].cost = 1;
        }
    }
    return 0;
}