最小路徑問題。
求完以后排序就可以了。
這題wa了一次。因為最近寫了好多有向圖的然后這個在讀入數(shù)據(jù)的時候忘記考慮這個是一個無向圖了。
1
#include<stdio.h>
2#include<string.h>
3int data[300][300],aa,bb,cc,a[300],b[300],n,m,i,j,k,t;
4int main()
5
{
6
while(1)
7
{
8 scanf("%d",&n);
9 if(n==0)break;
10 scanf("%d",&m);
11 memset(data,3,sizeof(data));
12 for(i=0;i<m;i++)
13 {
14 scanf("%d%d%d",&aa,&bb,&cc);
15 data[aa][bb]=cc;
16 data[bb][aa]=cc;
17
}
18 for(i=0;i<n;i++)data[i][i]=0;
19 for(k=0;k<n;k++)
20 for(i=0;i<n;i++)
21 for(j=0;j<n;j++)
22 if(data[i][k]+data[k][j]<data[i][j])
23 data[i][j]=data[i][k]+data[k][j];
24 for(i=0;i<n;i++)a[i]=data[0][i];
25 for(i=0;i<n;i++)b[i]=i;
26 for(i=0;i<n;i++)
27 for(j=0;j<n-1;j++)
28 if((a[j]>a[j+1]) || ((a[j]==a[j+1])&& b[j]>b[j+1]))
29 {
30 t=a[j];
31 a[j]=a[j+1];
32 a[j+1]=t;
33 t=b[j];
34 b[j]=b[j+1];
35 b[j+1]=t;
36 }
37
38 scanf("%d",&k);
39 printf("%d\n",b[k]);
40 }
41 return 0;
42
}
43