首页 > 代码库 > ACM2066
ACM2066
题目原址:http://acm.hdu.edu.cn/showproblem.php?pid=2066
大神必须飘过,我在这个题目里面学到了太多太多了。我提交了十六次,错了十二次,反复了这么久才解决内部的悬念。其实这个题目难度真心不大,但是却可以用很多种方式解决;
我知道的当然是用DIJKSTRA算法去解决;然后我把它改成各种形式去做这道题,一开始全错,就是找不到原因,后来才发现是一个数组开小了,因为它可以输入一千个数据,而她想要去的城市也可以输入一千个,相乘后上百万,我只开了一千的数组,这居然成为了一个主要错误原因。后来我干脆不用数组了,直接用一个变量操作;
解决方法一:
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=1200; 6 const int oo=1111111; 7 int maze[N][N],Mini[N]; 8 int used[N]; 9 int Upper; 10 void Dijkstra(int u)11 {12 memset(used,0,sizeof(used));13 memset(Mini,0,sizeof(Mini));14 int i,j,k;15 for(i=1;i<=Upper;i++)16 Mini[i]=maze[u][i];17 Mini[u]=0;18 used[u]=1;19 for(i=1;i<Upper;i++)20 {21 int mini=oo;22 for(j=1;j<=Upper;j++)23 {24 if(!used[j]&&Mini[j]<mini)25 {26 mini=Mini[j];27 k=j;28 }29 }30 used[k]=1;31 for(j=1;j<=Upper;j++)32 {33 if(!used[j]&&Mini[j]>Mini[k]+maze[k][j])34 Mini[j]=Mini[k]+maze[k][j];35 }36 }37 }38 int main()39 {40 int road,near,will;41 int Near[N],Will[N];42 while(scanf("%d %d %d",&road,&near,&will)==3)43 {44 for(int i=0;i<N;i++)45 {46 for(int j=0;j<N;j++)47 maze[i][j]=oo;48 }49 Upper=0;50 int start,end,value;51 for(int i=1;i<=road;i++)52 {53 scanf("%d %d %d",&start,&end,&value);54 int temp=(start>end)?start:end;55 Upper=(Upper>temp)?Upper:temp;56 if(value<maze[start][end])57 {58 maze[start][end]=value;59 maze[end][start]=value;60 }61 }62 int minnumber=oo;//原来我用的不是它,而是一个数组,那更麻烦,也容易犯错,还是这样比较简洁,且没有数组开小的风险63 for(int i=1;i<=near;i++)scanf("%d",&Near[i]);64 for(int i=1;i<=will;i++)scanf("%d",&Will[i]);65 for(int i=1;i<=near;i++)66 {67 Dijkstra(Near[i]);68 for(int j=1;j<=will;j++)69 if(Mini[Will[j]]<minnumber)70 minnumber=Mini[Will[j]];71 }72 printf("%d\n",minnumber);73 }74 return 0;75 }
在不断的犯错过程中,我便尝试了很多其他的办法,也让我非常欣喜的发现了下面的解决办法更加诱人,只是不如上面的容易理解;
因为他要求找出多个起点和结束点之间最短距离的最小值;其实可以把所有的起点都置为零,看作一个起点,从这个总的起点到所有其他点的最短距离就可以方便的求出来了;
所谓把所有的起点都置为零看作一个起点,是说把所有起点之间的距离看为零,这样从一个起点到另外一个起点是不需要任何距离的,然后找到一个起点到终点的最短路径,然后再判断其他起点到终点的最短路径;总之每个点记录的都是起点能到自己的最短距离;
这样值判断终点记录的值的大小就可以了;
input:
7 2 1
2 3 60
2 4 10
2 1 100
1 5 10
4 5 50
3 4 60
2 4 10
2 3
5
output
60
input:
8 2 1
2 3 60
2 4 10
2 1 100
1 5 10
4 5 50
3 4 60
2 4 10
1 3 30
2 3
5
output:
40
如上面图所示:
假如将编号为2 和 3 的点看作两个起始点,5 做为唯一终止点;
将编号2 3 存入数组begin[N]中;并设置2,3的low为零;
有代码for(int i=1;i<=upper;i++)//upper 代表输入的所有数据中的最大数,作为上届
Low[i]=oo;//初始化为无穷大,到达所有点的距离为无穷大
执行完上述步骤后,结果是:low[1]=low[2]=low[3]=low[4]=low[5]=无穷大(oo);
For(int i=1;i<=m;i++)m代表有m个临近城市
Low[begin[i]]=0;//将开始点的low设置为零,代表到达这两点的距离为零
此时结果是:low[2]=low[3]=0,其他的没变
Map[N][N]初始化:map[N][N]=oo;
用map[N][N]数组存储上图;//map数组中所有值初始化为无穷大
Map[1][2]=map[2][1]=100;
Map[2][3]=map[3][2]=60;
Map[1][5]=map[5][1]=10;
········
上述操作完成后,开始遍历操作
有代码:
For(int i=1;i<upper;i++)//要处理upper-1个点,因为最后一个点没有其他未处理的点和它比较了
{
Int Min=oo;int k=0;
For(int j=1;j<=upper;j++)
If(!vis[j]&&low[j]<Min)//vis[N]数组用来标记每一个点是否被处理;vis[i]=0;代表未访问
{ Min=low[j];
k=j;//标记最小元素的下标
}
Vis[k]=1;标记k元素的数为已访问过的
For(int j=1;j<=upper;j++)
If(!vis[j]&&low[j]>low[k]+map[j][k])
Low[j]=low[k]+map[j][k];
第一步遍历会搜索到k=2,因为一开始low[N]里面有两个零和三个无穷大,且k=2在3前面;
标记vis[2]=1;
从1开始搜索和未访问过的点:
1,未访问过,low[1]=oo>(low[k=2]=0)+(map[1][2]=100)=>更新Low[1]=100;
2,已访问;
3,未访问,low[3]=0<任何距离,不会更新
(由此可知,任何两个起点之间的距离都会一直为零,即起点的值不会更新)
4,未访问;low[4]=oo>(low[k=2]=0)+map[2][4]=10)?=true;所以low[4]更新为10;
5,未访问过;(low[5]=oo>(low[k=2]=0)+(map[2][5]=oo))=false=>low[5]不更新;
第一次完毕;
第二次搜索:搜到k=3;
标记vis[3]=1;
1,未访问;low[1]=100>(low[3]=0+map[1][3]=30)=true;=>更新low[1]=30;
2,,3已访问;
4,未访问;Low[4]=10>(low[3]=0+map[3][4]=60)=false;=>low[4]不更新
5,未访问;low[5]=oo>(low[3]=0+map[3][5]=oo)=false;=>low[5]不更新
第二次完毕;
经过上面两次搜索,得到下面结果:
Low[1]=30;low[2]=low[3]=0;low[4]=10;low[5]=oo;
第三次搜索到low[4]=10,k=4;
标记vis[4]=1;
1,未访问;low[1]=30>(low[4]=10+map[4][1]=oo)=false;=>不更新Low[1];
2,3,4已访问;
5,未访问;low[5]=oo>(low[4]=10+map[4][5]=50)=true;=>更新low[5]=60;
第三次搜索完毕;
此时结果是low[1]=30;low[2]=low[3]=0;low[4]=10;low[5]=60;
第四次搜到low[1]=30;k=1;
标记vis[1]=1;
1,2,3,4都已访问过;
5,未访问;low[5]=60>(low[1]=30+map[5][1]=10)=true;=>low[5]更新为40;
所有搜索完毕,此时得到正确答案;
Low[1]=30;low[2]=low[3]=0;low[4]=10;low[5]=40;
详细代码如下:
1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 using namespace std; 5 const int oo=11111111; 6 const int N=1200; 7 int map[N][N]; 8 int upper; 9 int begin[N];10 int low[N];11 int near,will;12 int vis[N];13 void dijkstra()14 {15 memset(vis,0,sizeof(vis));16 memset(low,0,sizeof(low));17 for(int i=1;i<=upper;i++)18 {19 low[i]=oo;20 }21 for(int i=1;i<=near;i++)22 {23 low[begin[i]]=0;24 //vis[begin[i]]=1;必须去掉这句25 }26 int k;27 for(int i=1;i<upper;i++)28 {29 int Min=oo;30 for(int j=1;j<=upper;j++)31 {32 if(!vis[j]&&low[j]<Min)33 {34 Min=low[j];35 k=j;36 }37 }38 vis[k]=1;39 for(int j=1;j<=upper;j++)40 {41 if(!vis[j]&&low[j]>low[k]+map[j][k])42 low[j]=low[k]+map[j][k];43 }44 }45 }46 int main()47 {48 int n;49 while(cin>>n>>near>>will)50 {51 for(int i=0;i<N;i++)52 for(int j=0;j<N;j++)53 map[i][j]=oo;54 int start,end,value;55 upper=0;56 for(int i=1;i<=n;i++)57 {58 scanf("%d %d %d",&start,&end,&value);59 int temp=start>end?start:end;60 upper=upper>temp?upper:temp;61 if(map[start][end]>value)62 map[start][end]=map[end][start]=value;63 }64 int mininum=oo;65 int te;66 for(int i=1;i<=near;i++)scanf("%d",&begin[i]);67 dijkstra();68 for(int i=1;i<=will;i++)69 {70 scanf("%d",&te);71 if(low[te]<mininum)mininum=low[te];72 }73 printf("%d\n",mininum);74 }75 return 0;76 }