Untitled

#include<iostream>
#include<string>
#include<vector>
#include<Climits>
#include<queue>
#include<tuple>
#include<unordered_map>

using namespace std;

class City
{
    friend class Graph;

    public:
        City(string name, int cost, int i)
        {   
            name = name;
            cost_value = cost;
            threshold = 0;
            refill_amount = 0;
            index = i;
        }

        void setvalue(int T, int S)
        {   
            isRefill = true;
            threshold = T;
            refill_amount = S;
        }

    private:
        int cost_value;
        int threshold;
        bool isRefill;
        int refill_amount;
        int index;
        string name;
        vector<City*> adjlist;
};

class Graph
{
    public:
        ~Graph(){}

        int getID(string& name)
        {
            auto id = nameToId.find(name);//回傳pair
            return (id == nameToId.end()) ? -1 : id->second;
        }
    
        Graph(int C, int R, int Cap, int V, int RE)
        {
            cities = C;
            roads = R;
            capacity = Cap;
            Vouchers = V;
            refill = RE;
            index = 0;
            citylist.resize(C);
            edge.resize(C);
        }

        void InsertCity(string name, int cost)
        {
            int id = index++;
            citylist[index] = new City(name,cost, id);
            nameToId[name] = id;
        }

        void InsertEdge(string name1, string name2, int edgecost)
        {   
            int ID1 = getID(name1);
            int ID2 = getID(name2);

            edge[ID1].push_back({ID2, edgecost});
            edge[ID2].push_back({ID1, edgecost});
        }

        void Set(string name, int T, int S)
        {
            int ID = getID(name);

            citylist[ID]->setvalue(T, S);
        }

        int Refill(int cityid, int food)
        {
            City* c = citylist[cityid];
            if(c->isRefill && food < c->threshold)
            {
                food = min(food + c->refill_amount, capacity);
            }

            return food;
        }

        long long Dijkstra(int src, int dst)
        {   
            vector<vector<vector<long long>>> dist
            (   
                cities,
                vector<vector<long long>>(capacity + 1, 
                    vector<long long>(Vouchers + 1, LLONG_MAX))
            );

            using State = tuple<long long, int, int, int>;
            //cost, city, food, vouchers_used
            priority_queue<State, vector<State>, greater<State>> pq;

            int startfood = Refill(src, 0);
            dist[src][startfood][0] = 0;
            pq.push({0, src, startfood, 0});

            while(!pq.empty())
            {

                auto [d, u, f, k] = pq.top();
                //cost, city, food, vouchers_used
                pq.pop();

                //d is cost
                if(d > dist[u][f][k]) continue;
                if(u == dst) return d;

                long long price = citylist[u]->cost_value;

                for (int fp = f + 1; fp <= capacity; ++fp) {           
                    int units_to_buy = fp - f;
                    int vouchers_can_use = min(units_to_buy, Vouchers - k);
                    
                    for (int x = 0; x <= vouchers_can_use; ++x) {      
                        int paid_units = units_to_buy - x;
                        long long nd = d + (long long)paid_units * price;
                        int new_k = k + x;
                        
                        if (nd < dist[u][fp][new_k]) 
                        {
                            dist[u][fp][new_k] = nd;
                            pq.push({nd, u, fp, new_k});
                        }
                    }
}

                for (auto& [v, w] : edge[u]) 
                {
                    if (w > f) continue;          
                    int nf = Refill(v, f - w);         
                    if (d < dist[v][nf][k]) 
                    {
                        dist[v][nf][k] = d;
                        pq.push({d, v, nf, k});
                    }
                }

            }

            return -1;   
        }
        
    private:
        //edge and cities
        unordered_map<string, int> nameToId;
        vector<City*> citylist;
        vector<vector<pair<int, int>>> edge; // city, distance
        City *start, *destination;

        //number
        int Vouchers;
        int cities;
        int roads;
        int capacity;
        int refill;
        int index;//the city id
        int food;
        
        //Dijkstra
        vector<long long> dist;
};

int main()
{
    int N;//Number of cities (1 ≤ N ≤ 1000)
    int M;//Number of undirected roads (1 ≤ M ≤ 105).
    int C;//Maximum food capacity (1 ≤ С ≤ 100).
    int K;//Number of free food vouchers (0 ≤ K ≤ 10).
    int R;//Number of cities that provide refills (0 ≤ R ≤ 10).

    cin >> N >> M >> C >> K >> R;

    cin.ignore();

    Graph g(N, M, C, K, R);

    string src, dst;

    for(int i = 0 ; i<N ; i++)
    {       
        string name;
        int v;
        cin >> name >> v;
        g.InsertCity(name, v);
    }

    for(int i = 0 ; i < M ; i++)
    {
        string u, v;
        int w;
        cin >> u >> v >> w;
        g.InsertEdge(u, v, w);
    }

    for(int i = 0 ; i<R ; i++)
    {
        string name;
        int T,S;
        cin >> name >> T >> S;
        g.Set(name, T, S);
    }

    cin >> src >> dst;

    int s = g.getID(src);
    int d = g.getID(dst);

    long long ans = g.Dijkstra(s, d);

    if(ans < 0) cout << "Impossible" << endl;
    else cout << ans << endl;

    return 0;
}