提供几道Dijkstra算法的ACM水题练习

发布网友发布时间：2022-05-16 20:22

共1个回答

热心网友时间：2023-12-16 04:10

浙江大学ZOJ上的1221题可以算是最最基础的Dijkstra算法练习。。

由于Dijkstra 与 prim 有惊人的相似之处，所以这道题要好好体会。。

希望对你有所帮助！！！！！

本人相当建议初学者做做。。下面是本人的AC代码：

#include<iostream>
#include<algorithm>
using namespace std;

int map[21][21];
int flag[21];
int length[21];
int dijkstra(int from,int to)
//Dijkstra算法真的跟Prim很像。。要好好体会体会。。
{
int q,w,m;
memset(flag,0,sizeof(flag));
memset(length,0,sizeof(length));
for(q=1;q<=20;q++)
length[q]=map[from][q];
flag[from]=1;
length[from]=0;
for(q=1;q<20;q++)
{
int min=9999,y;
for(w=1;w<=20;w++)
{
if(flag[w]==0&&min>=length[w])

min=length[w],y=w;
}
flag[y]=1;
for(w=1;w<=20;w++)
{
if(flag[w]==0&&map[y][w]==1&&length[w]>length[y]+1)

length[w]=length[y]+1;
}
}
return length[to];
}
int main()

//这是比较简单的求无向图无权任意两点的最短距离
{
int t,q,w,m,count=1;
while(scanf("%d",&t)!=EOF)
//一开始这里我写为：while(1)。。本来是想让他不停输入的。。谁知道TLE了。。
{
for(q=1;q<=20;q++)
for(w=1;w<=20;w++)

map[q][w]=1000;
while(t--)
{
scanf("%d",&w);
map[1][w]=map[w][1]=1;
}
for(q=2;q<20;q++)
{
scanf("%d",&t);
while(t--)
{

scanf("%d",&w);

map[q][w]=map[w][q]=1;
}
}
scanf("%d",&w);
//cout<<"Test Set #"<<count<<endl;
printf("Test Set #%d\
",count);
count++;
int from,to;
while(w--)
{

scanf("%d %d",&from,&to);
//cout<<from<<" to "<<to<<":"<<dijkstra(from,to)<<endl;
printf("%d to %d: %d\
",from,to,dijkstra(from,to));
}
printf("\
");
}
return 0;
}