时间: 1000ms / 空间: 655360KiB / Java类名: Main

背景

冬令营入学测试

描述

这个故事是关于小F的，它有一个怎么样的故事呢。

         小F是一个田径爱好者，这天它们城市里正在举办马拉松比赛，这个城市可以被看作是n个点m条带权有向边组成的图。马拉松比赛的终点只有一个：点S。

         有k个人参加了这场马拉松，小F所在的城市的马拉松与正常的马拉松不一样，每个人的起点都是不相同的，具体地，第i个人从第{ai}个城市出发，并且第i个人的速度是{vi}。每个人当然是会沿着最短路跑到S点，如果一个人跑步的距离是s，速度是v，那么他所花费的时间为s/v。

         现在小F想知道，谁是最快到达终点的。若有多个同时到达终点的，就求跑的路最长的，如果有多个同时到达终点且跑的路最长的，就求编号最大的。

         小F想知道那个人的编号是多少。

输入格式

第一行3个数字，n,k,m，表示点的个数，跑步的人数，以及路径的条数。

         接下来一行m行，每行3个数ai,bi,ci表示有一条从ai到bi长为ci的有向路径。

         接下来一行一个数S。

         接下来一行k个数，表示每个人的起点xi。

         接下来一行k个数，表示每个人的速度vi。

输出格式

输出一个数表示答案。

测试样例1

输入

5 2 10 

5 1 9 

1 2 81 

2 3 30 

2 1 46 

1 4 45 

2 4 48 

5 1 93 

2 5 61 

2 5 21 

3 5 45 

1 

3 5 

18 29

输出

2

备注

输入样例

3 2 3

1 2 2

1 3 3

2 3 1

3

2 1

1 3

输出样例

2

数据范围

对于30%的数据n<=5，m<=10。

对于100%的数据n<=300，m<=5000。0<=ci<=100，1<=xi,S<=n，1<=vi<=100，1<=k<=n。

 最短路问题，算出每个起点到终点的最短路，然后再算时间

堆优化的dijkstra代码：

#include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,k,m,x,y,z,s;int start[301],speed[301];//start存储起点，speed存储终点 double time[301];int minn_time;//花费时间最小的人的编号 int head[301];struct node{    int next,to,d;}e[10001];int DIS[301],cnt;void add(int u,int v,int w)//链表存储 {    cnt++;    e[cnt].to=v;    e[cnt].d=w;    e[cnt].next=head[u];    head[u]=cnt;}struct mon{    int num,dis;    bool operator < (mon k)const //大根堆改成小根堆     {        return dis>k.dis;    }};priority_queue
           
            p;//堆优化的spfa int main(){    scanf("%d%d%d",&n,&k,&m);    for(int i=1;i<=m;i++)    {        scanf("%d%d%d",&x,&y,&z);        add(y,x,z);//因为dijkstra是单源最短路径，所以从每个起点到达固定的终点，可以转化成从固定的起点到达每个终点。所以把x，y交换存储链表     }    scanf("%d",&s);    memset(DIS,127,sizeof(DIS));//dijkstra初始化     p.push((mon){s,0});    DIS[s]=0;    while(!p.empty())//dijikstra模板     {        mon now=p.top();        p.pop();        if(DIS[now.num]!=now.dis) continue;        for(int i=head[now.num];i;i=e[i].next)        {            if(DIS[now.num]+e[i].d
            
             ,==，
             <也能过 if(h<="0.00001&&h">
              =0)//相等 { if(DIS[i]>=DIS[start[minn_time]])//距离更大的 minn_time=i;//因为i从小到达枚举，所以更新的i一定比minn_time小 } else if(h<0)//当前的更小 minn_time=i; } else minn_time=i; } printf("%d",minn_time);}
             
            
           
          
         
        
       

floyed代码：

#include
       
        using namespace std;int a[301][301];int n,k,m,s;int x,y,z;int xi[301],vi[301];double minx=999999;int jl,jlk;int main(){    cin>>n>>k>>m;    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            if(a[i][j]==0&&i!=j) a[i][j]=999999;    for(int i=1;i<=m;i++)    {        cin>>x>>y>>z;        a[x][y]=z;    }    for(int kk=1;kk<=n;kk++)        for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++)            {                if(i!=j&&i!=kk&&j!=kk)                {                    a[i][j]=min(a[i][j],a[i][kk]+a[kk][j]);                }            }    cin>>s;    for(int i=1;i<=k;i++)        cin>>xi[i];    for(int i=1;i<=k;i++)        cin>>vi[i];    for(int i=1;i<=k;i++){        if(a[xi[i]][s]*1.0/vi[i]<=minx){            if(a[xi[i]][s]*1.0/vi[i]==minx){                if(a[xi[i]][s]>=a[jlk][s]){                    minx=a[xi[i]][s]*1.0/vi[i];                    jl=i;                    jlk=xi[i];                }            }            else{                minx=a[xi[i]][s]*1.0/vi[i];                jl=i;                jlk=xi[i];            }        }    }    cout<