我这个感觉本地能做了，但杭电oj过不了，有人可以看看吗，题目链接:
Problem - 2066
http://acm.hdu.edu.cn/showproblem.php?pid=2066%EF%BC%8C%E6%9D%AD%E7%94%B52066%E9%A2%98
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int dis[1010],que_top=0,que_wei=0;//dis是储存到每个城市的距离，队列的头尾
struct node* que[100000];//队列
int like[1010];//想到的城市
struct node
{
int num;//城市编号
int quan;//花费时间
int vis;//访问标记
struct node*parent;//对应表头
struct node*next;
};
void tianjia(struct node*fp1,struct node*fp2)//添加相连的城市
{
if(fp1->next!=NULL)
fp2->next=fp1->next;
fp1->next=fp2;
fp2->parent=fp1;
}
struct node* create(int nu,int qua)//创造新节点，nu是城市标号，qua是这条路的权重
{
struct node* new1;
new1=(struct node*)malloc(sizeof(struct node));
new1->num=nu;
new1->quan=qua;
new1->vis=0;
new1->next=NULL;
return new1;
};
void quepush(struct node* fp)//入队
{
que[que_wei]=fp;
que_wei=que_wei+1;
if(que_wei==100000)
que_wei=0;
}
struct node* quepop()//出队
{
struct node* new=que[que_top];
que_top=que_top+1;
if(que_top==100000)
que_top=0;
return new;
};
void inque(struct node* fp ,struct node* vter[])//进行bfs,输入的是表头和表头的集合
{
if(fp->next==NULL)
return ;
//如果该城市有相连的城市，且这个城市没有被访问过，这个城市需要的时间为表头城市的时间加这个节点的权重，并把该节点对应的城市表头入队，且将该节点对应的城市表头设置为已访问过
if(fp->next!=NULL&&vter[fp->next->num]->vis==0){
dis[fp->next->num]=dis[fp->next->parent->num]+fp->next->quan;
quepush(vter[fp->next->num]);
vter[fp->next->num]->vis=1;
inque(fp->next,vter);//搜索该表头后面还有没有其他去的城市}
//如果该城市有相连的城市，且这个城市被访问过，再计算出这条路径下这个城市需要的时间为表头城市的时间加这个节点的权重，与之前的算出的时间作比较，取小的，不再入队
if(fp->next!=NULL&&vter[fp->next->num]->vis==1){
int di=dis[fp->next->parent->num]+fp->next->quan;
if(di<dis[fp->next->num])
dis[fp->next->num]=di;
inque(fp->next,vter);//搜索该表头后面还有没有其他去的城市}
}
//释放表头后的节点的动态内存
void qing(struct node*fp)
{
if(fp->next==NULL)
return ;
struct node*pp=fp->next->next;
free(fp->next);
fp->next=pp;
qing(fp);
}
int main()
{
struct node* vter[1010];//表头集合，也是城市
int T,S,D,a,b,time,c;
int top=0;//这个是喜欢城市个数，也是数组存到哪里了的标记
int min;
for(int i=0;i<1010;i++)
{
vter[i]=(struct node*)malloc(sizeof(struct node));
vter[i]->next=NULL;
vter[i]->num=i;
vter[i]->vis=0;
}//初始化表头
while(scanf("%d %d %d",&T,&S,&D)!=EOF){
for(int i=0;i<T;i++)
{
scanf("%d %d %d",&a,&b,&time);
struct node* new1=create(b,time);
struct node* new2=create(a,time);
tianjia(vter[a],new1);
tianjia(vter[b],new2);
}//添加边，也是城市的联系
for(int i=0;i<S;i++)
{
scanf("%d",&c);
struct node* new=create(c,0);
tianjia(vter[0],new);
}//添加邻近城市，时间权重设为0
for(int i=0;i<D;i++)
{
int e;
scanf("%d",&e);
like[top]=e;
top++;
}//喜欢城市的编号，个数
dis[0]=0;//起点位置时间为0
quepush(vter[0]);//将起点入队
while(que_top!=que_wei)
{
struct node* curr=quepop();
inque(curr,vter);
}//bfs直到队列为空
min=dis[like[0]];
for(int i=1;i<top;i++)
{
if(min>dis[like[i]])
min=dis[like[i]];
}//找出最短时间
printf("%d\n",min);
//清空这组测试的数据
for(int i=0;i<1010;i++)
{
dis[i]=0;
qing(vter[i]);
vter[i]->vis=0;
vter[i]->next=NULL;
}
top=0;
que_top=0;
que_wei=0;
}
return 0;
}
