描述
Once,in a kingdom,there are N cities.M roads have been buit such that from one
city you can reach any other cities.Between any two cities there is at most one
road.But after a series war,D road are destoryed.The king wants to repair the
road system.There are two important cities A and B,The king wants to make
the two cities connected as soon as possible.Now it is your job to repair some
roads such that A and B are connected and the length of all roads repaired is
minimun.
输入
Input may
contain seveal test data sets.
For each data set, the first line contain an
integer N(2<N<100),indicating the number of cities.The cities are
numbered from 1 To N.then the second line contains an integer M (
N-1<M<N*(N-1)/2),indicating the number of roads.Next come M lines,each
contains three integers I,J,K,which means that there is a road between I and
J,whose length is K.
Then next line contains an integer
D(1<=D<=M),indicating the number of roads which are destoryed.The
following D lines each contain two integer I,J,which means that the road which
directly connected city I and J has been destoryed.
The last line
contains two integer A,B,indicating the two important cities.
Input is ended by N = 0,which should not be processed.
输出
For each test case,just output one line with the total length of the roads needed to repair such that A and B are connected.If we could not raech B from A,output"-1".
样例输入
3
2
1 2 1
2 3 2
1
1 2
1 3
0
样例输出
1
每个城市之间都有一些路连接，某些城市之间的有遭到了破坏，现在要求我们求修路的最短长度。
如果修完所有的路也无法保证通行则输出-1。
逆向思维，让城市之间已经存在的路的长度为0，需要修补的初始化要修补的路的长度。这样就变成了简单的单源最短路径问题了。
#include <stdio.h>#include <string.h>#define MAXN 110#define inf 0x3f3f3f3fint N;int m1[MAXN][MAXN];int m2[MAXN][MAXN];int dist[MAXN];int
visited[MAXN];void
dijkstra(int
begin){ int
i,j,k; k=begin; for(j=1; j<=N; j++){ visited[j]=0; if(j!=k){ dist[j]=m2[k][j]; } } visited[k]=1; for(i=1;i<N-1;i++){ int
min=inf; k=0; for(j=1; j<=N; j++){ if(!visited[j]&&dist[j]<min){ min=dist[j]; k=j; } } if(k==0)break; visited[k]=1; for(j=1; j<=N; j++){ if(!visited[j]&& dist[k]+m2[k][j]<dist[j]){ dist[j]=dist[k]+m2[k][j]; } } } }int
main(){ int
M,D,a,b,c; int
B,E; while( scanf("%d",&N)!=EOF && N){ for( int
i=1 ;i<=N; i++ ){ for( int
j=1; j<=N; j++ ){ if(i==j)m2[i][j]=0; else
m2[i][j]=inf; } } scanf("%d",&M); for( int
i=0; i<M; i++ ){ scanf("%d%d%d",&a,&b,&c); m1[a][b]=c; m1[b][a]=c; m2[a][b]=0; m2[b][a]=0; } scanf("%d",&D); for( int
i=0; i<D; i++ ){ scanf("%d%d",&a,&b); m2[a][b]=m1[a][b]; m2[b][a]=m1[b][a]; } scanf("%d%d",&B,&E); dijkstra(B); if(dist[E]==inf){ printf("-1\n"); }else{ printf("%d\n",dist[E]); } } return
0;} |
原文：http://www.cnblogs.com/chenjianxiang/p/3544452.html