Dowemo

Problem Description (,, ~ ),, (, ^0^ ),,,.,,,,,,.,,,,,. Because the home is on a city, there's no train passing, so she can only go to the nearby city.
Input There are multiple sets of input data, the first line of each group is three integer t, s and d, which indicates that there's a t, and the
Then there are three lines, each line has three integer a, b, time, representing a, b city between the drive is the time hour; ( 1 = <( a, b ) <= 1000; a, there may be multiple paths between b.
And then the number of s + 1 lines, which represents the city connected to the grass.
And then the number of d + 2 lines of the line, which indicates the.

Output And the output to a of the city.
Sample Input




6 2 3


1 3 5


1 4 7


2 8 12


3 8 4


4 9 12


9 10 2


1 2


8 9 10






Sample Output 9 Solve the problem: A problem, the data range of the question is a bit, in the case of 1000,, but the data isn't the worst case, that's, the. Here's the 202ms, and the time is, and if you use, it should be less. Code:

#include<stdio.h>


#include<string.h>


int s1[1010][1010];


int main() 


{


 int i,s,t,d,j,k,m,t1,t2,t3;


 while(scanf("%d%d%d",&s,&t,&d)!=EOF)


 {


 for(i=0;i<=1000;i++)


 {


 for(j=0;j<=1000;j++)


 s1[i][j]=99999999;


 }


 m=0;


 for(i=0;i<s;i++)


 {


 scanf("%d%d%d",&t1,&t2,&t3);


 if(s1[t1][t2]>t3)


 {


 s1[t1][t2]=t3;


 s1[t2][t1]=t3;}


 if(m<t1)


 m=t1;


 if(m<t2)


 m=t2; 


 }


 for(i=0;i<t;i++)


 {


 scanf("%d",&t3);


 s1[0][t3]=0;


 s1[t3][0]=0;


 }


 for(k=0;k<=m;k++)


 {


 for(i=0;i<=m;i++)


 {


 if(s1[i][k]!=99999999)//这里减少时间复杂度,当能到达松弛点时才进入循环。


 for(j=0;j<=m;j++)


 {


 if(s1[i][j]>s1[i][k]+s1[k][j])


 s1[i][j]=s1[i][k]+s1[k][j];


 }


 }


 }


 m=99999999;


 for(i=0;i<d;i++)


 {


 scanf("%d",&t1);


 if(m>s1[0][t1])


 m=s1[0][t1];


 }


 printf("%dn",m); 


 }


 return 0;


}









Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs