# Saving James Bond - Hard Version

This time let us consider the situation in the movie “Live and Let Die” in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape – he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot). Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him a shortest path to reach one of the banks. The length of a path is the number of jumps that James has to make.

## Input Specification

Each input file contains one test case. Each case starts with a line containing two positive integers $N (≤100)$, the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x,y) location of a crocodile. Note that no two crocodiles are staying at the same position.

## Output Specification

For each test case, if James can escape, output in one line the minimum number of jumps he must make. Then starting from the next line, output the position (x,y) of each crocodile on the path, each pair in one line, from the island to the bank. If it is impossible for James to escape that way, simply give him 0 as the number of jumps. If there are many shortest paths, just output the one with the minimum first jump, which is guaranteed to be unique.

## Sample Input 1

17 15
10 -21
10 21
-40 10
30 -50
20 40
35 10
0 -10
-25 22
40 -40
-30 30
-10 22
0 11
25 21
25 10
10 10
10 35
-30 10

## Sample Output 1

4
0 11
10 21
10 35

## Sample Input 2

4 13
-12 12
12 12
-12 -12
12 -12

## Sample Output 2

0

## 参考代码

#include<iostream>
#include<cmath>
#include<stack>
#define MaxVertexNum 101
using namespace std;
typedef struct Point{
int x,y;
}point;
double G[MaxVertexNum][MaxVertexNum];
point P[MaxVertexNum];
void Dijikstra(int,int,int),BuildGraph(int,int),Save007(int,int);
double canjump(point,point,int),dist[MaxVertexNum]={0};
int FindMindist(int),path[MaxVertexNum][MaxVertexNum];
bool canescape(point,int),firstjump(point,int),collected[MaxVertexNum]={false};
int main(int argc,char*argv[]) {
int n,jump;
cin>>n>>jump;
BuildGraph(n,jump);
Save007(n,jump);
}
void BuildGraph(int n,int jump){
int i,j;
for(i=1;i<=n;i++)cin>>P[i].x>>P[i].y;
for(i=0;i<=n;i++)for(j=0;j<=n;j++)if(i!=j)G[i][j]=INFINITY;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i!=j&&canjump(P[i],P[j],jump)!=0)
G[i][j]=G[j][i]=canjump(P[i],P[j],jump);
}
void Save007(int n,int jump){
int i,j,mini=1,minj;
stack<int> s;
double mind=INFINITY;
for(i=1;i<=n;i++)if(!collected[i]&&firstjump(P[i],jump)){
for(j=1;j<=n;j++)dist[j]=INFINITY;
Dijikstra(i,n,jump);
for(j=1;j<=n;j++)if(canescape(P[j],jump)&&mind>dist[j])mind=dist[j],mini=i,minj=j;
}
if(mind<INFINITY){
for(i=minj;i!=mini;i=path[mini][i])s.push(i);
s.push(mini);
cout<<s.size()+1<<endl;
while(!s.empty()){
cout<<P[s.top()].x<<' '<<P[s.top()].y<<endl;
s.pop();
}
}else cout<<0<<endl;
}
bool firstjump(point p,int jump){
return sqrt(pow(p.x,2)+pow(p.y,2))<=jump;
}
bool canescape(point p,int jump){
return (p.x+jump>=50||p.x-jump<=-50||p.y+jump>=50||p.y-jump<=-50);
}
double canjump(point p1,point p2,int jump){
double d;
if((d=(sqrt(pow(p1.x-p2.x,2)+pow(p1.y-p2.y,2))))<=jump)return d;
return 0;
}
int FindMindist(int n){
double mindist=INFINITY;
int mini=1;
for(int i=1;i<=n;i++)if(!collected[i]&&dist[i]<mindist)
mindist=dist[i],mini=i;
if(mindist<INFINITY)return mini;
else return -1;
}
void Dijikstra(int s,int n,int jump){
int count=2;
for(int i=1;i<=n;i++){
dist[i]=G[s][i];
if(dist[i]<INFINITY)path[s][i]=s;
else path[s][i]=-1;
}
dist[s]=0,collected[s]=true;
while(true){
int v = FindMindist(n);
collected[v]=true,count++;
if (v < 0)break;
for (int i = 1; i <= n; i++)
if (!collected[i] && G[v][i] < INFINITY)
if (dist[i] > dist[v] + G[v][i]) {
dist[i] = dist[v] + G[v][i];
path[s][i] = v;
}
}
} 

# Gas Station

A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. However it must guarantee that all the houses are in its service range. Now given the map of the city and several candidate locations for the gas station, you are supposed to give the best recommendation. If there are more than one solution, output the one with the smallest average distance to all the houses. If such a solution is still not unique, output the one with the smallest index number.

## Input Specification

Each input file contains one test case. For each case, the first line contains 4 positive integers: $N (≤10^3)$, the total number of houses; $M (≤10)$, the total number of the candidate locations for the gas stations; $K (≤10^4)$, the number of roads connecting the houses and the gas stations; and DS, the maximum service range of the gas station. It is hence assumed that all the houses are numbered from 1 to N, and all the candidate locations are numbered from G1 to GM.Then K lines follow, each describes a road in the format

P1 P2 Dist

where P1 and P2 are the two ends of a road which can be either house numbers or gas station numbers, and Dist is the integer length of the road.

## Output Specification

For each test case, print in the first line the index number of the best location. In the next line, print the minimum and the average distances between the solution and all the houses. The numbers in a line must be separated by a space and be accurate up to 1 decimal place. If the solution does not exist, simply output No Solution.

## Sample Input 1

4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2

## Sample Output 1

G1
2.0 3.3

## Sample Input 2

2 1 2 10
1 G1 9
2 G1 20

## Sample Output 2

No Solution

## ac代码

#include<iostream>
#include<cstdlib>
#define MaxHouses 1000
#define MaxStation 10
#define INFINITY 65535
using namespace std;
int G[MaxHouses+MaxStation+1][MaxHouses+MaxStation+1],dist[MaxHouses+MaxStation+1];
bool collected[MaxHouses+MaxStation+1];
void Buildgraph(int,int,int,int);
void GasStation(int,int,int);
bool Dijkstra(int,int,int,int);
int FindMindist(int,int,int);
int main(int argc,char*argv[]) {
int n,m,k,ds;
cin>>n>>m>>k>>ds;
Buildgraph(n,k,m,ds);
GasStation(n,ds,m);
}
void Buildgraph(int n,int k,int m,int ds){
int g1,g2,l;char s1,s2;
for(int i=1;i<=n+m;i++)for(int j=1;j<=n+m;j++)if(i!=j)G[i][j]=INFINITY;
for(int i=1;i<=k;i++){
cin>>s1>>s2>>l;
g1=(s1=='G'?atoi(s1+1)+n:atoi(s1));
g2=(s2=='G'?atoi(s2+1)+n:atoi(s2));
G[g1][g2]=G[g2][g1]=l;
}
}
void GasStation(int n,int ds,int m){
double mina=INFINITY;int mini=0,mind=0;
for(int i=n+1;i<=n+m;i++){
for(int j=1;j<=n+m;j++)collected[j]=false;
if(Dijkstra(n,m,i,ds)){
int min=INFINITY;double ave=0;
for(int j=1;j<=n;j++){
ave+=dist[j];
if(min>dist[j]&&i!=j)min=dist[j];
}
ave=ave/n;
if(mind<min||(mind==min&&mina>ave))mina=ave,mind=min,mini=i;
}
}
if(mina<INFINITY){
cout<<'G'<<mini-n<<endl;
printf("%.1f %.1f\n",(double)mind,mina);
}else cout<<"No Solution"<<endl;
}
bool Dijkstra(int n,int m,int s,int ds){
for(int i=1;i<=n+m;i++)dist[i]=G[s][i];
collected[s]=true,dist[s]=0;
while(true){
int v=FindMindist(n,m,ds);
if(v<0)break;
collected[v]=true;
for(int i=1;i<=n+m;i++)if(!collected[i]&&G[v][i]<INFINITY)
if(dist[i]>dist[v]+G[v][i])dist[i]=dist[v]+G[v][i];
}
for(int i=1;i<=n;i++)if(dist[i]>ds)return false;
return true;
}
int FindMindist(int n,int m,int ds){
int mind=INFINITY,mini=-1;
for(int i=1;i<=n+m;i++)if(!collected[i]&&mind>dist[i])
mind=dist[i],mini=i;
if(mind<INFINITY)return mini;
return -1;
}   

Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness.

## Input Specification

Each input file contains one test case. For each case, the first line contains 2 positive integers $N (2≤N≤200)$, the number of cities, and K, the total number of routes between pairs of cities; followed by the name of the starting city. The next N−1 lines each gives the name of a city and an integer that represents the happiness one can gain from that city, except the starting city. Then K lines follow, each describes a route between two cities in the format City1 City2 Cost. Here the name of a city is a string of 3 capital English letters, and the destination is always ROM which represents Rome.

## Output Specification

For each test case, we are supposed to find the route with the least cost. If such a route is not unique, the one with the maximum happiness will be recommanded. If such a route is still not unique, then we output the one with the maximum average happiness – it is guaranteed by the judge that such a solution exists and is unique. \Hence in the first line of output, you must print 4 numbers: the number of different routes with the least cost, the cost, the happiness, and the average happiness (take the integer part only) of the recommanded route. Then in the next line, you are supposed to print the route in the format :

City1->City2->…->ROM.

## Sample Input

6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1

## Sample Output

3 3 195 97
HZH->PRS->ROM

## 参考代码

#include<iostream>
#include<stack>
#define INFINITY 65535
#define MaxCities 205
using namespace std;
typedef struct City{
string name;
int happiness;
}city;
city cities[MaxCities];
int G[MaxCities][MaxCities],cost[MaxCities],paths[MaxCities],
num[MaxCities],happiness[MaxCities],path[MaxCities];
bool collected[MaxCities]={false};
void BuildGraph(int,int);
void Dijkstra(int,int);
int FindMindist(int);
int main(int argc,char*argv[]) {
int n,k;
string start;
cin>>n>>k>>start;
cities[n-1].name=start;
BuildGraph(n,k);
}
void BuildGraph(int n,int k){
string c1,c2;int d,i1,i2;
for(int i=0;i<n-1;i++)cin>>cities[i].name>>cities[i].happiness;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(i!=j)G[i][j]=INFINITY;
for(int i=0;i<k;i++){
cin>>c1>>c2>>d;
for(int j=0;j<n;j++)
if(c1==cities[j].name)i1=j;
else if(c2==cities[j].name)i2=j;
G[i1][i2]=G[i2][i1]=d;
}
}
stack<int> s;int ave=0,count=1,rom;
Dijkstra(n,n-1);
for(int i=0;i<n-1;i++)if(cities[i].name=="ROM")rom=i;
for(int i=path[rom];i!=n-1;i=path[i],count++){
s.push(i);
ave+=happiness[i];
}
printf("%d %d %d %d\n",num[rom],cost[rom],happiness[rom],(ave+cities[rom].happiness)/count);
cout<<cities[n-1].name<<"->";
while(!s.empty()){
cout<<cities[s.top()].name<<"->";
s.pop();
}
cout<<"ROM"<<endl;
}
void Dijkstra(int n,int s){
for(int i=0;i<n;i++){
cost[i]=G[s][i],num[i]=1,happiness[i]=cities[i].happiness;
if(cost[i]<INFINITY)path[i]=s,paths[i]=1;
else path[i]=-1;
}
collected[s]=true,cost[s]=0,paths[s]=0;
while(true){
int v=FindMindist(n);
collected[v]=true;
if(v<0)break;
for(int i=0;i<n;i++)if(!collected[i]&&G[v][i]<INFINITY){
if(cost[i]>cost[v]+G[v][i])
cost[i]=cost[v]+G[v][i],num[i]=num[v],path[i]=v,
paths[i]=paths[v]+1,happiness[i]=happiness[v]+cities[i].happiness;
else if(cost[i]==cost[v]+G[v][i]){
num[i]+=num[v];
if(happiness[i]<happiness[v]+cities[i].happiness)
happiness[i]=happiness[v]+cities[i].happiness,path[i]=v,paths[i]=paths[v]+1;
else if(happiness[i]==happiness[v]+cities[i].happiness&&
happiness[i]/paths[i]<(happiness[v]+cities[i].happiness)/(paths[v]+1))path[i]=v,paths[i]=paths[v]+1;
}
}
}
}
int FindMindist(int n){
int minc=INFINITY,mini=-1;
for(int i=0;i<n;i++)if(!collected[i]&&minc>cost[i])
minc=cost[i],mini=i;
if(minc<INFINITY)return mini;
else return -1;
}