Expert.
Put your skills to the test.

Problem summary

Airports lie on a sphere centered at the origin. Each allowed undirected flight consumes a given integer amount of fuel and follows the shortest spherical arc at constant speed V. Some airports refill the tank to capacity C immediately on arrival, with no time cost. Starting with a full tank at S, find the minimum time to reach T, or report0 if impossible.

Source clarification. Restored from retained completed-algorithm notes and original statement after workspace maintenance. Prior version had independent expanded-state Bellman–Ford tests; fresh strict/sample checks are reported separately for the reconstruction.

Constraints

2≤N≤1000;1≤M≤10000;1≤V≤1000 (up to3 decimals);1≤C≤1000; coordinates in[−100,100] with up to18 decimals. All airports lie on one sphere with integer radius≥1, up to10^−10 deviation. There are1…20 refueling airports, S is one. Each unordered pair appears at most once; endpoints differ;1≤F≤C; flight arcs have length≥10^−6.

Worked example

Original two-column sample reconstructed in reading order. Optimal routes1–2–6–4–3 and1–4–6–4–3 refill at6 and traverse four90° arcs. Total time2π·5/2.5=4π.

6 9 2.5 9
0 5 0 1
0 0 -5 0
0 -5 0 0
0 0 5 0
3 4 0 0
4 3 0 1
1 2 5
2 3 8
1 4 5
4 3 5
1 5 1
5 6 9
5 2 1
2 6 2
6 4 4
1 3

12.5663706144

Solution analysis

1. A single best time per airport is insufficient: a slightly slower arrival with more fuel can enable a flight that the fastest arrival cannot take. Expand the state to(vertex,remaining fuel), with fuel0…C. At refueling airports normalize every arrival to fuel C, because replenishing is mandatory, free, and never harmful.
2. Compute each flight time geometrically. If position vectors are u and v on the same sphere, their central angle is atan2(|u×v|,u·v), in[0,π]. The shortest arc length is R times this angle, so flight time is R·angle/V. atan2 is stable near both coincident and antipodal vectors, where naive acos rounding can be troublesome. Store coordinates and times as long double.
3. From state(v,f), consider only flights requiring at most f fuel. After reaching a non-refueling neighbor, the new fuel is f−F; at a refueling neighbor it becomes C. Add the precomputed flight time to the state distance. Every transition has positive weight, so ordinary Dijkstra with a priority queue applies to this expanded graph.
4. Initialize only(S,C) at time0. Ignore stale heap entries. The first settled state whose airport is T is the minimum among all fuel levels at T; arrival with zero fuel is allowed. If the queue empties without reaching T, print the source’s required0 sentinel rather than a negative value.
5. Worked example: with capacity9, the direct airport sequences1–2–3 and1–4–3 require13 and10 fuel, so both fail without refilling. Airport6 refills the tank. Route1–2–6 reaches it using7 fuel, refills to9, then6–4–3 uses4+5=9. The four shortest arcs are each90° on radius5; time is4·(π·5/2)/2.5=12.5663706144.
6. The code stores only the original airport adjacency lists and generates state edges on demand. There is no need to build millions of explicit expanded edges. Refilling is represented directly in transitions instead of adding zero-time refill edges. A lazy heap is straightforward, but its worst-case memory can exceed the distance table because multiple improved entries may coexist.

Why it works

Any feasible itinerary corresponds to a path through expanded states, since every transition checks the exact fuel requirement and applies the required refill rule. Conversely every expanded path corresponds to a feasible itinerary with identical flight time. Precomputed arc weights are the physical travel times. Dijkstra is valid for nonnegative weights and settles states in shortest-time order, so the first target state gives the minimum feasible itinerary time. Exhausting reachable states proves impossibility.

Watch out. Fuel cost is not flight time; geometry supplies time separately. Refilling happens on arrival, and S starts full. Preserve different fuel states at non-refueling vertices. Use radians in arc calculations, not degrees. Do not treat an arc passing geometrically through another airport as an extra flight. Reaching T with no remaining fuel is legal. Output0 for unreachable as specified.

An independently written complete program with standard headers.

#include<cmath>
#include<functional>
#include<iomanip>
#include<iostream>
#include<limits>
#include<queue>
#include<tuple>
#include<vector>
using namespace std;
struct Point{
    long double x;
    long double y;
    long double z;
};
struct Flight{
    int to;
    int fuel;
    long double time;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,capacity;
    long double speed;
    cin>>n>>m>>speed>>capacity;
    vector<Point>point(n+1);
    vector<int>refill(n+1);
    for(int i=1;i<=n;++i){
        cin>>point[i].x>>point[i].y>>point[i].z>>refill[i];
    }
    long double radius=sqrtl(point[1].x*point[1].x+point[1].y*point[1].y+point[1].z*point[1].z);
    vector<vector<Flight>>graph(n+1);
    for(int i=0;i<m;++i){
        int a,b,fuel;
        cin>>a>>b>>fuel;
        Point u=point[a];
        Point v=point[b];
        long double dot=u.x*v.x+u.y*v.y+u.z*v.z;
        long double x=u.y*v.z-u.z*v.y;
        long double y=u.z*v.x-u.x*v.z;
        long double z=u.x*v.y-u.y*v.x;
        // atan2 is stable for nearly coincident and antipodal points.
        long double angle=atan2l(sqrtl(x*x+y*y+z*z),dot);
        long double time=radius*angle/speed;
        graph[a].push_back({b,fuel,time});
        graph[b].push_back({a,fuel,time});
    }
    int start,target;
    cin>>start>>target;
    const long double infinity=numeric_limits<long double>::infinity();
    vector<vector<long double>>distance(n+1,vector<long double>(capacity+1,infinity));
    using State=tuple<long double,int,int>;
    priority_queue<State,vector<State>,greater<State>>pending;
    distance[start][capacity]=0;
    pending.push({0,start,capacity});
    while(!pending.empty()){
        auto[time,vertex,fuel]=pending.top();
        pending.pop();
        if(time!=distance[vertex][fuel]){
            continue;
        }
        if(vertex==target){
            cout<<fixed<<setprecision(10)<<time<<'\n';
            return 0;
        }
        for(const Flight&edge:graph[vertex]){
            if(edge.fuel>fuel){
                continue;
            }
            int nextFuel=refill[edge.to]?capacity:fuel-edge.fuel;
            long double candidate=time+edge.time;
            if(candidate<distance[edge.to][nextFuel]){
                distance[edge.to][nextFuel]=candidate;
                pending.push({candidate,edge.to,nextFuel});
            }
        }
    }
    cout<<"0\n";
}