HDU2433(SPFA)

剛開始用dijkstra()+暴力枚舉，然後就超時了。後來看了題解才知道這題的關鍵所在：用sum[i]來存以i為起點的最短路之和，ans表示i從1到n的sum[i]的和，然後摧毀道路之後，以u為起點，看能不能到達v，如果能到達，同時也就說明了以v為起點也能到達u，因為路是雙向的，則以u，v為起點，保存它們的最短路之和，答案就是ans-sum[u]-sum[v]+num1+num2；若不能到達，則直接輸出INF。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define maxn 105
#define INF 99999999
#define LL long long
using namespace std;

struct Edge
{
	int from,to,len;
	int next;
}edge[maxn*60];
int n,m,k;
int sum[maxn];
int vis[maxn];
int dis[maxn];
int head[maxn*30];
int u[maxn*30],v[maxn*30];

void AddEdge(int u,int v)
{
	edge[k].from=u;
	edge[k].to=v;
	edge[k].len=1;
	edge[k].next=head[u];
	head[u]=k++;

	edge[k].from=v;
	edge[k].to=u;
	edge[k].len=1;
	edge[k].next=head[v];
	head[v]=k++;
}

void init()
{
	memset(sum,0,sizeof(sum));
	memset(head,-1,sizeof(head));
}

int SPFA(int s)
{
	for(int i=0;i<=n;i++)
	{
		dis[i]=INF;
		vis[i]=0;
	}
	queue q;
	dis[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].len)
			{
				dis[v]=dis[u]+edge[i].len;
				if(vis[v]==0)
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	int Sum=0;
	for(int i=1;i<=n;i++)
		Sum+=dis[i];
	return Sum;
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		k=1;
		init();
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&u[i],&v[i]);
			AddEdge(u[i],v[i]);
		}
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			sum[i]=SPFA(i);
			ans+=sum[i];
		}
		for(int i=1;i<=m;i++)
		{
			edge[i*2].len=INF;
			edge[i*2-1].len=INF;
			int num1=SPFA(u[i]);
			if(dis[v[i]]>=INF)
				printf("INF\n");
			else
			{
				int num2=SPFA(v[i]);
				printf("%d\n",ans+num1+num2-sum[u[i]]-sum[v[i]]);
			}
			edge[i*2].len=1;
			edge[i*2-1].len=1;
		}
	}
	return 0;
}