Planet Teleports
National Olympiad — National round
Submission name: teleports.cpp
Problem summary
Planets are identified by coordinate pairs. Listed teleports connect pairs of planets in both directions; each use costs 10. Find the cheapest journey between the two specified planets.
Input
Start x y and destination x y; n; then n records x₁ y₁ x₂ y₂ describing teleports.
Output
Minimum cost, or exactly no solution if unreachable.
Constraints
1 ≤ n ≤ 2000; all coordinates are integers in [1,10000].
Worked example
An independently prepared example for this explanation.
Input
1 2 5 6 2 1 2 3 4 3 4 5 6
Output
20
Solution analysis
- Compress coordinate pairs into vertex IDs and add undirected edges.
- BFS finds the minimum number of teleport uses. Multiply by 10.
Why it works
All edges have the same positive cost, so minimizing cost is equivalent to minimizing edge count, exactly what BFS computes.
Watch out. Coordinates label vertices; Euclidean distances do not determine travel cost.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: All edges have the same positive cost, so minimizing cost is equivalent to minimizing edge
// count, exactly what BFS computes.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<utility>
#include<tuple>
using namespace std;
int main(){
map<pair<int,int>,int>id;
vector<vector<int>>g;
auto get=[&](int x,int y){
pair<int,int>p={x,y};
if(id.count(p)){
return id[p];
}
int v=g.size();
id[p]=v;
g.push_back({});
return v;
};
int x,y,a,b;
cin>>x>>y>>a>>b;
int start=get(x,y),target=get(a,b),n;
cin>>n;
while(n--){
cin>>x>>y>>a>>b;
int u=get(x,y),v=get(a,b);
g[u].push_back(v);
g[v].push_back(u);
}
vector<int>d(g.size(),-1);
queue<int>q;
q.push(start);
d[start]=0;
while(!q.empty()){
int v=q.front();
q.pop();
for(int u:g[v]){
if(d[u]<0){
d[u]=d[v]+1;
q.push(u);
}
}
}
if(d[target]<0){
cout<<"no solution\n";
}
else{
cout<<10*d[target]<<'\n';
}
}