HDU2145 SPFA

题意：给定一些人，这些人要到同一个地点去，求最先到达的人。
spfa（反向加边就行）水~
View Code
  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<stdlib.h>
  4 #include<queue>
  5 #include<algorithm>
  6 using namespace std;
  7 const int maxn = 315;
  8 const int maxm = 5015;
  9 const int inf = 9999999;
 10 int cnt,head[ maxn ];
 11 int n,m,k;
 12 int dis[ maxn ],vis[ maxn ];
 13 struct node{
 14     int u,val,next;
 15 }edge[ maxm ];
 16 struct node2{
 17     int city_number,dis;
 18     double speed,time;
 19     int p_number;//p_number is for the number of the people
 20 }p[ maxn ];
 21 void init(){
 22     cnt=0;
 23     memset( head,-1,sizeof( head ));
 24 }
 25 void addedge( int a,int b,int c ){
 26     edge[ cnt ].u=b;
 27     edge[ cnt ].val=c;
 28     edge[ cnt ].next=head[ a ];
 29     head[ a ]=cnt++;
 30 }
 31 int cmp( node2 a,node2 b ){
 32     if( a.time!=b.time )
 33         return a.time<b.time;
 34     else if( a.dis!=b.dis )
 35         return a.dis>b.dis;
 36     else
 37         //return a.city_number>b.city_number;
 38         return a.p_number>b.p_number;
 39 }
 40 
 41 void spfa( int s ){
 42     for( int i=1;i<=n;i++ ){
 43         dis[ i ]=inf;
 44         vis[ i ]=0;
 45     }
 46     queue<int>q;
 47     while( !q.empty() )
 48         q.pop();
 49     dis[ s ]=0;
 50     vis[ s ]=1;
 51     q.push( s );
 52     while( !q.empty() ){
 53         int now=q.front();
 54         q.pop();
 55         vis[ now ]=0;
 56         for( int i=head[ now ];i!=-1;i=edge[ i ].next ){
 57             int next=edge[ i ].u;
 58             if( dis[ next ]>dis[ now ]+edge[ i ].val ){
 59                 dis[ next ]=dis[ now ]+edge[ i ].val;
 60                 if( vis[ next ]==0 ){
 61                     vis[ next ]=1;
 62                     q.push( next );
 63                 }
 64             }
 65         }
 66     }
 67     return ;
 68 }
 69 
 70 int main(){
 71     while( scanf("%d%d%d",&n,&m,&k)!=EOF ){
 72         int a,b,c;
 73         init();
 74         while( k-- ){
 75             scanf("%d%d%d",&a,&b,&c);
 76             addedge( b,a,c );//change the dir
 77         }
 78         int zz_pos;
 79         scanf("%d",&zz_pos);
 80         for( int i=1;i<=m;i++ ){
 81             scanf("%d",&p[i].city_number);
 82         }
 83         for( int i=1;i<=m;i++ ){
 84             scanf("%lf",&p[i].speed);
 85         }
 86         spfa( zz_pos );//the aim to all the vet,get dis[ maxn ]
 87         for( int i=1;i<=m;i++ ){
 88             p[i].p_number=i;
 89             if( dis[ p[i].city_number ]>=inf ){
 90                 p[i].time=1.0*inf;
 91                 p[i].dis=inf;
 92             }
 93             else{
 94                 p[i].dis=dis[ p[i].city_number ];
 95                 p[i].time=dis[ p[i].city_number ]*1.0/(1.0*p[i].speed);
 96             }
 97         }
 98         sort( p+1,p+1+m,cmp );
 99         if( p[1].time>=(1.0*inf) ){
100             printf("No one\n");
101         }
102         else{
103             printf("%d\n",p[1].p_number);
104         }
105     }
106     return 0;
107 }
keep moving...