求距離一個(gè)city第k近的city。根據(jù)dijkstra的特點(diǎn)，循環(huán)K+1次即找到了距源點(diǎn)距離第K近的。
Code：
1 #include<iostream>
2 #define M 1000000000
3 #define MAX 202
4 int map[MAX][MAX],dis[MAX];
5 bool flag[MAX];
6 void dijkstra(int n,int s,int key) // n is the number of point,and start from s ,key is the key-city
7 {
8 int i,j,k,temp,md;
9 memset(flag,false,sizeof(flag));
10 for(i=0;i<MAX;i++)
11 dis[i]=M;
12 dis[s]=0;
13 for(i=1;i<=key+1;i++)
14 {
15 md=M;
16 for(j=0;j<n;j++) //找到距離當(dāng)前最近的
17 {
18 if(!flag[j]&&dis[j]<md)
19 {
20 md=dis[j];
21 temp=j;
22 }
23 }
24 flag[temp]=true; //將這個(gè)點(diǎn)加進(jìn)來(lái)
25 for(j=0;j<n;j++) //松弛操作
26 {
27 if(!flag[j]&&md+map[temp][j]<dis[j])
28 dis[j]=md+map[temp][j];
29 }
30 }
31 printf("%d\n",temp);
32 }
33 int main()
34 {
35 int i,j,k,m,n,p;
36 while(scanf("%d",&n)!=EOF)
37 {
38 if(n==0) break;
39 scanf("%d",&m);
40 for(i=0;i<MAX-1;i++)
41 for(j=i+1;j<MAX;j++)
42 map[i][j]=map[j][i]=M;
43 for(i=1;i<=m;i++)
44 {
45 scanf("%d%d%d",&j,&k,&p);
46 map[j][k]=map[k][j]=p;
47 }
48 scanf("%d",&k);
49 dijkstra(n,0,k);
50 }
51 return 0;
52 }
53