3897 - 道路重建
【问题描述】
从前有个王国，王国有N个城市，M条道路。两个城市之间最多只有一条道路。战争过后，有D条道路被摧毁了。国王想重建道路，使得最重要的两个城市A和B互通。
你的工作就是决定重建哪些道路能使得AB相连并且重建的道路的长度总和最少。
【输入格式】
有多组测试数据。
每组测试数据的第一行为一个整数N（2 < N≤100），表示城市的数目。城市的编号为1、2、3…N。
第二行为一个整数M(N-1≤M≤N*(N-1)/2),表示道路的数目。
下来M行，每行三个整数I，J，K（1≤I,J≤N,I≠J,0 < K≤100）,表示I和J之间有直接的道路长度为K。
下来一行为一个整数D（1≤D≤M），表示被摧毁的道路的数目。
下来D行每行两个整数I，J，表示城市I和J之间的道路被摧毁。
最后一行为两个整数A和B。表示两个重要的城市。
输入当N=0时结束，并且不做任何处理。
【输出格式】
每组测试数据输出一行，输出重建道路的长度的总和的最小值。
Input
3
2
1 2 1
2 3 2
1
1 2
1 3
0
Output
1
Input
Output
Examples
Input
3 2 1 2 1 2 3 2 1 1 2 1 3 0
Output
1
Solution C++
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> using namespace std; struct node{ int x,y,d,next; }a[21000];int len,last[11000]; void ins(int x,int y,int d){ len++; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len; } int n,m,d[110],head,tail,list[110];bool v[110],kt[110][110]; int main(){ int t; while(scanf("%d",&n)){ if(n==0)return 0; len=0;memset(last,0,sizeof(last)); scanf("%d",&m); for(int i=1;i<=m;i++){ int x,y,c; scanf("%d%d%d",&x,&y,&c); ins(x,y,c); ins(y,x,c); } scanf("%d",&m);memset(kt,false,sizeof(kt)); for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); kt[x][y]=true; kt[y][x]=true; } int st,ed; scanf("%d%d",&st,&ed); for(int i=1;i<=n;i++)d[i]=999999999;d[st]=0; memset(v,false,sizeof(v));v[st]=true; head=1;tail=2;list[1]=st; while(head!=tail){ int x=list[head]; for(int k=last[x];k>0;k=a[k].next){ int y=a[k].y; if(kt[a[k].x][a[k].y]==true){ if(d[y]>d[x]+a[k].d){ d[y]=d[x]+a[k].d; if(v[y]==false){ v[y]=true; list[tail++]=y; if(tail==n+1)tail=1; } } } else{ if(d[y]>d[x]){ d[y]=d[x]; if(v[y]==false){ v[y]=true; list[tail++]=y; if(tail==n+1)tail=1; } } } } head++; v[x]=false; if(head==n+1)head=1; } printf("%d\n",d[ed]); } }