[TYVJ] P1238 路径

 1 #include<stdio.h>
 2 #include<string.h>
 3 int i,j,n,m,k,x,y,z,a[110][110],
 4     mx=351111;
 5 int 
 6 pre(void)
 7 {
 8     memset(a,2,sizeof(a));
 9     return 0;
10 }
11 
12 int
13 add(int x,int y,int z)
14 {
15     if ((mx+z)<a[x][y]) 
16         a[x][y]=z+mx;
17     return 0;
18 }
19 
20 int 
21 min(int a,int b)
22 {
23     if (a<b) return(a);
24     else return(b);
25 }
26 
27 int
28 init(void)
29 {
30     scanf("%d%d",&m,&n);
31     for(i=1;i<=n;i++)
32     {
33         scanf("%d%d%d",&x,&y,&z);
34         add(x,y,z);
35     }
36     return 0;
37 }
38 
39 int 
40 main(void)
41 {
42     pre();
43     init();
44     
45     for(k=0;k<=m-1;k++)
46         for(i=0;i<=m-1;i++)
47             for(j=0;j<=m-1;j++)
48             if ((i!=j)&&(i!=k)&&(k!=j))
49             a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
50     
51     printf("%d\n",a[0][1]%mx);
52     return 0;
53 }
54