本題描述了一個(gè)連接不同城市的道路系統(tǒng)，N個(gè)城市之間有M條道路，給出邊的權(quán)值。其中有D條道路被破壞，這將導(dǎo)致兩個(gè)非常重要的城市A和B之間的通訊中斷?，F(xiàn)在要修復(fù)被破壞一些已經(jīng)被破壞的道路，使A和B可以通訊，且使總總造價(jià)最小。

對(duì)于這題，我的思路是：對(duì)于被破壞的公路，權(quán)值為原來(lái)的權(quán)值；沒(méi)有被破壞的，因?yàn)椴恍枰亟?，即重建的造價(jià)為0，所以權(quán)值修改為0，轉(zhuǎn)化為了求A和B之間最短路徑的題目。

我是用begin[i]和end[i]記錄被破壞道路的起點(diǎn)和終點(diǎn)，這樣做需要注意一點(diǎn)，即在構(gòu)造新圖的時(shí)候，必須仍舊是無(wú)向圖。為了代碼的簡(jiǎn)潔，程序中用到了goto語(yǔ)句。

我的代碼如下：

#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;
}