HDu 2145最短絡
http://acm.hdu.edu.cn/showproblem.php?pid=2145
问题补充:n个の点があって、m个人、k本は道があって、1つの终点Sを与えて、m个人の起点とスピード、最初に终点に着く者を求めて、もし“同时に”は谁の距离に着いて远くて谁が胜って、もし“同时に距离”の谁の番号は大きい谁が胜ちます;
考え方:終点からDijkstraを1回使い、m個人の時間、距離、番号を構造resultに記入し、要求通りにソートして出力する.
问题补充:n个の点があって、m个人、k本は道があって、1つの终点Sを与えて、m个人の起点とスピード、最初に终点に着く者を求めて、もし“同时に”は谁の距离に着いて远くて谁が胜って、もし“同时に距离”の谁の番号は大きい谁が胜ちます;
考え方:終点からDijkstraを1回使い、m個人の時間、距離、番号を構造resultに記入し、要求通りにソートして出力する.
#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
",result[0].num);
else
printf("No one
");
}
return 0;
}