首页 > 代码库 > 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 存入数组begin[N]中;并设置23low为零;

有代码forint 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=ooint 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=23前面;

标记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;

1234都已访问过;

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 }