本题描述了一个连接不同城市的道路系统，N个城市之间有M条道路，给出边的权值。其中有D条道路被破坏，这将导致两个非常重要的城市A和B之间的通讯中断。现在要修复被破坏一些已经被破坏的道路，使A和B可以通讯，且使总总造价最小。
对于这题，我的思路是：对于被破坏的公路，权值为原来的权值；没有被破坏的，因为不需要重建，即重建的造价为0，所以权值修改为0，转化为了求A和B之间最短路径的题目。
我是用begin[i]和end[i]记录被破坏道路的起点和终点，这样做需要注意一点，即在构造新图的时候，必须仍旧是无向图。为了代码的简洁，程序中用到了goto语句。
我的代码如下：
#include<stdio.h>
#define MAXN 101
#define MAXINT 200000000
long n,m,d,a,b,g[MAXN][MAXN],begin[220],end[220];
void solve()
{
long i,j,k,min,g2[MAXN][MAXN],dist[MAXN],visit[MAXN];
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{
if(g[i][j]!=MAXINT)
g2[i][j]=0;
else g2[i][j]=MAXINT;
}
for(i=1;i<=d;i++)
{
g2[begin[i]][end[i]]=g[begin[i]][end[i]];
g2[end[i]][begin[i]]=g[end[i]][begin[i]];
}
// Init
for(i=0;i<=n;i++)
visit[i]=0;
visit[a]=1;
for(i=1;i<=n;i++)
dist[i]=g2[a][i];
dist[a]=0;
for(i=1;i<=n;i++)
{
min=MAXINT;
k=0;
for(j=1;j<=n;j++)
if(!visit[j]&&dist[j]<min)
{
min=dist[j];
k=j;
}
if(k==0) break;
visit[k]=1;
for(j=1;j<=n;j++)
if(!visit[j]&&dist[k]+g2[k][j]<dist[j])
dist[j]=dist[k]+g2[k][j];
}
printf("%ld\n",dist[b]);
}
void run()
{
long i,j,t1,t2,w;
RUN_BEGIN:
scanf("%ld",&n);
if(n==0) return;
scanf("%ld",&m);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
g[i][j]=MAXINT;
for(i=1;i<=m;i++)
{
scanf("%ld%ld%ld",&t1,&t2,&w);
g[t1][t2]=w;
g[t2][t1]=w;
}
scanf("%ld",&d);
for(i=1;i<=d;i++)
scanf("%ld%ld",&begin[i],&end[i]);
scanf("%ld%ld",&a,&b);
solve();
goto RUN_BEGIN;
}
int main()
{
freopen("rebuild.in","r",stdin);
freopen("rebuild.out","w",stdout);
run();
return 0;
}
posted on 2010-01-06 19:56
lee1r 阅读(449)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论