1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 struct Edge 7 { 8     int to;  //边终点 9     int w;   //边值10     int next;//结构体模拟链表11 }edge[50005];12 int m,n,target,outqueue[305],used[305],head[305],dis[305],start[305],speed[305];13 int spfa(int sta)14 {15     int temp,i;16     queue
         
          q;17     while (!q.empty()) q.pop();18     used[sta]=1; dis[sta]=0; q.push(sta);19     while (!q.empty())20     {21         temp=q.front(); q.pop();22         outqueue[temp]++; used[temp]=0;23         if (outqueue[temp]>n) return -1;24         for (i=head[temp];i!=-1;i=edge[i].next)25         if (dis[edge[i].to]>dis[temp]+edge[i].w)26         {27             dis[edge[i].to]=dis[temp]+edge[i].w;28             if (used[edge[i].to]==0)29             {30                 used[edge[i].to]=1;31                 q.push(edge[i].to);32             }33         }34     }35     return 1;36 }37 int main()38 {39     int i,k,a,b,w,judge,maxdis,x;40     double min;41     while (~scanf("%d%d%d",&n,&m,&k))42     {43         memset(outqueue,0,sizeof(outqueue));//出队次数判断负权回路44         memset(used,0,sizeof(used));//用不用加入队列45         memset(head,-1,sizeof(head));//数组模拟链表46         for (i=1;i<=n;i++) dis[i]=10000000;47         for (i=1;i<=k;i++)48         {49             scanf("%d%d%d",&b,&a,&w);50             edge[i].to=b;51             edge[i].w=w;52             edge[i].next=head[a];53             head[a]=i;54         }55         scanf("%d",&target);56         for (i=1;i<=m;i++) scanf("%d",&start[i]);57         for (i=1;i<=m;i++) scanf("%d",&speed[i]);58         min=10000000.0; maxdis=0;59         judge=spfa(target);60         for (i=1;i<=m;i++)61         {62             x=dis[start[i]];63             if (x!=10000000&&(1.0*x/speed[i]
          
           =maxdis)))64 { min=1.0*x/speed[i]; maxdis=x; judge=i; }65 }66 if (fabs(min-10000000.0)<1e-6) printf("No one\n");67 else printf("%d\n",judge);68 }69 }