hdu 2145 最短路

題目大意：有n個點，m個人，k條有向路，給出一個終點S，m個人的起點和速度，求最先到達終點者，若“同時”到達誰的距離遠誰勝，若“同時同距離”誰的編號大誰勝；

思路：從終點開始用一次Dijkstra，將m個人的時間，距離，編號記入結構result中，按要求排序輸出；

[cpp]
#include<iostream>  
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
using namespace std; 
#define Max 30005  
int map[305][305],flag[305],dist[305],S,n,m,k; 
struct node 
{ 
    int num,dist; 
    double time; 
}result[305]; 
int cmp(const void* a,const void* b) 
{ 
    if((*(struct node*)a).time==(*(struct node*)b).time){ 
        if((*(struct node*)a).dist==(*(struct node*)b).dist){ 
            return (*(struct node*)b).num-(*(struct node*)a).num; 
        } 
        else 
            return (*(struct node*)b).dist-(*(struct node*)a).dist; 
 
    } 
    else 
        return (*(struct node*)a).time>(*(struct node*)b).time?1:-1; 
} 
void Dijkstra() 
{ 
    int i,j,node; 
    memset(flag,0,sizeof(flag)); 
    for(i=1;i<=n;i++)dist[i]=map[S][i]; 
    flag[S]=1; 
    for(i=1;i<=n;i++){ 
        int min=Max; 
        for(j=1;j<=n;j++){ 
            if(!flag[j]&&dist[j]<min){ 
                min=dist[j]; 
                node=j; 
            } 
        } 
        if(min==Max)break; 
        flag[node]=1; 
        for(j=1;j<=n;j++){ 
            if(!flag[j]&&dist[j]>dist[node]+map[node][j]) 
                dist[j]=dist[node]+map[node][j]; 
        } 
    } 
} 
int main() 
{ 
    int i,j,position[305],speed[305]; 
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){ 
        for(i=1;i<=n;i++){ 
            for(j=1;j<=n;j++){ 
                map[i][j]=(i==j?0:Max); 
            } 
        } 
        int a,b,c; 
        for(i=0;i<k;i++){ 
            scanf("%d%d%d",&a,&b,&c); 
            map[b][a]=(map[b][a]<c?map[b][a]:c); 
        } 
        scanf("%d",&S); 
        for(i=0;i<m;i++)scanf("%d",&position[i]); 
        for(i=0;i<m;i++)scanf("%d",&speed[i]); 
        Dijkstra(); 
        for(i=0;i<m;i++){ 
            result[i].num=i+1; 
            result[i].dist=dist[position[i]]; 
            result[i].time=result[i].dist*1.0/speed[i]; 
        } 
        qsort(result,m,sizeof(result[0]),cmp); 
        if(result[0].dist!=Max) 
            printf("%d\n",result[0].num); 
        else 
            printf("No one\n"); 
    } 
    return 0; 
} 

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
#define Max 30005
int map[305][305],flag[305],dist[305],S,n,m,k;
struct node
{
 int num,dist;
 double time;
}result[305];
int cmp(const void* a,const void* b)
{
 if((*(struct node*)a).time==(*(struct node*)b).time){
  if((*(struct node*)a).dist==(*(struct node*)b).dist){
   return (*(struct node*)b).num-(*(struct node*)a).num;
  }
  else
   return (*(struct node*)b).dist-(*(struct node*)a).dist;

 }
 else
  return (*(struct node*)a).time>(*(struct node*)b).time?1:-1;
}
void Dijkstra()
{
 int i,j,node;
 memset(flag,0,sizeof(flag));
 for(i=1;i<=n;i++)dist[i]=map[S][i];
 flag[S]=1;
 for(i=1;i<=n;i++){
  int min=Max;
  for(j=1;j<=n;j++){
   if(!flag[j]&&dist[j]<min){
    min=dist[j];
    node=j;
   }
  }
  if(min==Max)break;
  flag[node]=1;
  for(j=1;j<=n;j++){
   if(!flag[j]&&dist[j]>dist[node]+map[node][j])
    dist[j]=dist[node]+map[node][j];
  }
 }
}
int main()
{
 int i,j,position[305],speed[305];
 while(scanf("%d%d%d",&n,&m,&k)!=EOF){
  for(i=1;i<=n;i++){
   for(j=1;j<=n;j++){
    map[i][j]=(i==j?0:Max);
   }
  }
  int a,b,c;
  for(i=0;i<k;i++){
   scanf("%d%d%d",&a,&b,&c);
   map[b][a]=(map[b][a]<c?map[b][a]:c);
  }
  scanf("%d",&S);
  for(i=0;i<m;i++)scanf("%d",&position[i]);
  for(i=0;i<m;i++)scanf("%d",&speed[i]);
  Dijkstra();
  for(i=0;i<m;i++){
   result[i].num=i+1;
   result[i].dist=dist[position[i]];
   result[i].time=result[i].dist*1.0/speed[i];
  }
  qsort(result,m,sizeof(result[0]),cmp);
  if(result[0].dist!=Max)
   printf("%d\n",result[0].num);
  else
   printf("No one\n");
 }
 return 0;
}