题目原址：http://acm.hdu.edu.cn/showproblem.php?pid=2066
大神必须飘过，我在这个题目里面学到了太多太多了。我提交了十六次，错了十二次，反复了这么久才解决内部的悬念。其实这个题目难度真心不大，但是却可以用很多种方式解决；
我知道的当然是用DIJKSTRA算法去解决；然后我把它改成各种形式去做这道题，一开始全错，就是找不到原因，后来才发现是一个数组开小了，因为它可以输入一千个数据，而她想要去的城市也可以输入一千个，相乘后上百万，我只开了一千的数组，这居然成为了一个主要错误原因。后来我干脆不用数组了，直接用一个变量操作；
解决方法一：
1 #include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
const int oo=;
int maze[N][N],Mini[N];
int used[N];
int Upper;
void Dijkstra(int u)
{
memset(used,,sizeof(used));
memset(Mini,,sizeof(Mini));
int i,j,k;
for(i=;i<=Upper;i++)
Mini[i]=maze[u][i];
Mini[u]=;
used[u]=;
for(i=;i<Upper;i++)
{
int mini=oo;
for(j=;j<=Upper;j++)
{
if(!used[j]&&Mini[j]<mini)
{
mini=Mini[j];
k=j;
}
}
used[k]=;
for(j=;j<=Upper;j++)
{
if(!used[j]&&Mini[j]>Mini[k]+maze[k][j])
Mini[j]=Mini[k]+maze[k][j];
}
}
}
int main()
{
int road,near,will;
int Near[N],Will[N];
while(scanf("%d %d %d",&road,&near,&will)==)
{
for(int i=;i<N;i++)
{
for(int j=;j<N;j++)
maze[i][j]=oo;
}
Upper=;
int start,end,value;
for(int i=;i<=road;i++)
{
scanf("%d %d %d",&start,&end,&value);
int temp=(start>end)?start:end;
Upper=(Upper>temp)?Upper:temp;
if(value<maze[start][end])
{
maze[start][end]=value;
maze[end][start]=value;
}
}
int minnumber=oo;//原来我用的不是它，而是一个数组，那更麻烦，也容易犯错，还是这样比较简洁，且没有数组开小的风险
for(int i=;i<=near;i++)scanf("%d",&Near[i]);
for(int i=;i<=will;i++)scanf("%d",&Will[i]);
for(int i=;i<=near;i++)
{
Dijkstra(Near[i]);
for(int j=;j<=will;j++)
if(Mini[Will[j]]<minnumber)
minnumber=Mini[Will[j]];
}
printf("%d\n",minnumber);
}
return ;
}
在不断的犯错过程中，我便尝试了很多其他的办法，也让我非常欣喜的发现了下面的解决办法更加诱人，只是不如上面的容易理解；
因为他要求找出多个起点和结束点之间最短距离的最小值；其实可以把所有的起点都置为零，看作一个起点，从这个总的起点到所有其他点的最短距离就可以方便的求出来了；
所谓把所有的起点都置为零看作一个起点，是说把所有起点之间的距离看为零，这样从一个起点到另外一个起点是不需要任何距离的，然后找到一个起点到终点的最短路径，然后再判断其他起点到终点的最短路径；总之每个点记录的都是起点能到自己的最短距离；
这样值判断终点记录的值的大小就可以了；
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;
详细代码如下：
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int oo=;
const int N=;
int map[N][N];
int upper;
int begin[N];
int low[N];
int near,will;
int vis[N];
void dijkstra()
{
memset(vis,,sizeof(vis));
memset(low,,sizeof(low));
for(int i=;i<=upper;i++)
{
low[i]=oo;
}
for(int i=;i<=near;i++)
{
low[begin[i]]=;
//vis[begin[i]]=1;必须去掉这句
}
int k;
for(int i=;i<upper;i++)
{
int Min=oo;
for(int j=;j<=upper;j++)
{
if(!vis[j]&&low[j]<Min)
{
Min=low[j];
k=j;
}
}
vis[k]=;
for(int j=;j<=upper;j++)
{
if(!vis[j]&&low[j]>low[k]+map[j][k])
low[j]=low[k]+map[j][k];
}
}
}
int main()
{
int n;
while(cin>>n>>near>>will)
{
for(int i=;i<N;i++)
for(int j=;j<N;j++)
map[i][j]=oo;
int start,end,value;
upper=;
for(int i=;i<=n;i++)
{
scanf("%d %d %d",&start,&end,&value);
int temp=start>end?start:end;
upper=upper>temp?upper:temp;
if(map[start][end]>value)
map[start][end]=map[end][start]=value;
}
int mininum=oo;
int te;
for(int i=;i<=near;i++)scanf("%d",&begin[i]);
dijkstra();
for(int i=;i<=will;i++)
{
scanf("%d",&te);
if(low[te]<mininum)mininum=low[te];
}
printf("%d\n",mininum);
}
return ;
}