HDU2433Travel(SPFA+記錄路徑優化)

Travel

Time Limit: 10000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1847    Accepted Submission(s): 623

Problem Description       One day, Tom traveled to a country named BGM. BGM is a small country, but there are N (N <= 100) towns in it. Each town products one kind of food, the food will be transported to all the towns. In addition, the trucks will always take the shortest way. There are M (M <= 3000) two-way roads connecting the towns, and the length of the road is 1.

      Let SUM be the total distance of the shortest paths between all pairs of the towns. Please write a program to calculate the new SUM after one of the M roads is destroyed.

Input       The input contains several test cases.

      The first line contains two positive integers N, M. The following M lines each contains two integers u, v, meaning there is a two-way road between town u and v. The roads are numbered from 1 to M according to the order of the input.

      The input will be terminated by EOF.

Output       Output M lines, the i-th line is the new SUM after the i-th road is destroyed. If the towns are not connected after the i-th road is destroyed, please output “INF” in the i-th line.

Sample Input

5 4
5 1
1 3
3 2
5 4
2 2
1 2
1 2
        

Sample Output

INF
INF
INF
INF
2
2
        

Source 2008 Asia Chengdu Regional Contest Online  

題意：每次隻能删除一條邊，問每個點到所有點的最短路徑總和最小。隻要任意兩個點之間沒有路的就輸出 INF。

#include<stdio.h>
#include<queue>
using namespace std;
const int N = 105;
const int inf = 99999999;
struct EDG
{
    int u,v,id;
};
vector<EDG>mapt[N];
int dis[N],n,numEdg[N][N],father[N],goEdg[N][N][N],sum[N];

void spfa(int id,int s,bool b)
{
    queue<int>q;
    int inq[N]={0};
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    q.push(s);
    dis[s]=0; father[s]=s;
    while(!q.empty())
    {
        s=q.front(); q.pop();
        inq[s]=0;
        int len=mapt[s].size();
        for(int i=0;i<len;i++)
        if(id!=mapt[s][i].id)
        {
            int v=mapt[s][i].v;
            if(dis[v]>dis[s]+1)
            {
                dis[v]=dis[s]+1;
                if(b)
                 father[v]=s;
                if(inq[v]==0)
                    inq[v]=1,q.push(v);
            }
        }
    }
}
int main()
{
    int m,a,b;
    EDG ss,edg[N*30];
    while(scanf("%d%d",&n,&m)>0)
    {
        for(int i=1;i<=n;i++)
        {
            mapt[i].clear();
            for(int j=1;j<=n;j++)
            {
                numEdg[i][j]=0;
                for(int e=1;e<=n;e++)
                goEdg[i][j][e]=0;
            }
        }

        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            edg[i].u=a; edg[i].v=b;
            numEdg[a][b]++; numEdg[b][a]++;
            if(numEdg[a][b]>1)
             continue;
            ss.id=i;
            ss.v=b; mapt[a].push_back(ss);
            ss.v=a; mapt[b].push_back(ss);
        }
        int SUM=0;
        for(int i=1;i<=n;i++)
        {
            spfa(-1,i,true);
            sum[i]=0;
            for(int j=1;j<=n;j++)
            if(dis[j]==inf)
            {
                sum[i]=inf; break;
            }
            else sum[i]+=dis[j];
            if(sum[i]==inf)
            {
               SUM=inf; break;
            }
            SUM+=sum[i];
            for(int j=1;j<=n;j++)
            {
                int u,v=j;
                while(father[v]!=v)
                {
                    u=father[v];
                    goEdg[i][u][v]=goEdg[i][v][u]=1;
                    v=u;
                }
            }
        }
        int ans;
        for(int id=1;id<=m;id++)
        {
            if(SUM==inf)
            {
                printf("INF\n"); continue;
            }
            else if(numEdg[edg[id].u][edg[id].v]>1)
            {
                printf("%d\n",SUM); continue;
            }
            ans=0;
            for(int i=1;i<=n;i++)
            if(goEdg[i][edg[id].u][edg[id].v])//最主要的優化
            {
                spfa(id,i,false);
                for(int j=1;j<=n;j++)
                 if(dis[j]==inf)
                {
                    ans=inf; break;
                }
                else ans+=dis[j];
                if(ans==inf)
                    break;
            }
            else ans+=sum[i];
            if(ans==inf)
                printf("INF\n");
            else printf("%d\n",ans);
        }
    }
}