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)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(103)N (≤10^3), the total number of houses; M(10)M (≤10), the total number of the candidate locations for the gas stations; K(104)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

分析

本题输出的是Gas Station与全部居民楼中的最短距离中距离最长的候选点,Gas Station与居民楼的距离最长不能超过ds,否则直接淘汰该候选点。如果该距离相等的话找到其中距离居民楼的平均距离最短的候选点输出,两种距离都相等的话输出序号最小的那一个候选点。在计算Gas Station与居民楼距离的时候需要将m个候选Gas Station全部纳入图中,因为输入中给出了居民楼和候选地址之间的边,但是计算平局距离和最短距离时只能在Gas Station与居民楼的距离中计算。输入中存在字符’G’,因此存储输入的变量类型为char[],因为n<=1000,所以数组长度至少为4。

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[5],s2[5];
    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[0]=='G'?atoi(s1+1)+n:atoi(s1));
        g2=(s2[0]=='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;
}   

All Roads Lead to Rome

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(2N200)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

分析

在Dijkstra算法,上增加了相等时的两次特判及不同最短路径条数的计算

参考代码

#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 LeadtoRome(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);
    LeadtoRome(n);
}
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;
    }
}
void LeadtoRome(int n){
    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;
}