Submission

[PPxSSSSSSSSSSSSSSSSS]

Score: 0

User: Jibhong

Problemset: C.Love Sick

Language: cpp

Time: 0.003 second

Submitted On: 2025-01-28 20:35:58

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int pos;
    int dist;
    int pot;
    int out;

    Node(int p, int d, int po, int o) : pos(p), dist(d), pot(po), out(o) {}

    bool operator>(const Node& other) const {
        if(out==other.out)
            return pot < other.pot;
        return out > other.out;
    }
};

int main() {
    // Initialize 'edge' with appropriate values
    int n,e,p;
    cin>>n>>e>>p;
    int u,v,w;

    const int maxn = n+1; // Example value for maximum number of nodes
    const int start_pos = 0; // Starting position (example)
    const int destination = n-1; // Destination node
    const int max_potions = 11; // Maximum number of potions
    vector<vector<pair<int, int>>> edge(maxn); 
    
    for(int i=0;i<n;++i){
        cin>>u>>v>>w;
        edge[u].push_back({v,w});
        edge[v].push_back({u,w});
    }
    priority_queue<Node,vector<Node>,greater<Node>> pq;
    vector<vector<int>> visited(maxn, vector<int>(10 + 1, INT_MAX)); // Using INT_MAX for initialization

    pq.push(Node(start_pos, 0, p, 0));
    visited[start_pos][max_potions] = 0;

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        
//         cout<<current.pos<<' '<<current.dist<<' '<<current.pot<<' '<<(current.out > 0 ? current.out : 0)<<'\n'; 
        if (current.pos == destination) {
            int min_HP = current.out;
            cout<< (min_HP > 0 ? min_HP : 0) +1; 
            return 0; 
        }

        for (int i = 0; i < edge[current.pos].size(); ++i) {
            pair<int, int> neighbor = edge[current.pos][i];
            int new_dist = current.dist + neighbor.second; // Assuming the second element is cost
            int out_temp = max(current.out, new_dist);

//             if (new_dist >= 0) { 
                if (visited[neighbor.first][current.pot] > new_dist) {
                    visited[neighbor.first][current.pot] = new_dist;
                    pq.push(Node(neighbor.first, new_dist, current.pot, out_temp));
                }
//             }

            if (current.pot > 0) { // Ensure there's a potion to use
                new_dist = current.dist - neighbor.second;
                int back_out_temp = max(current.out, new_dist);
                if (visited[neighbor.first][current.pot - 1] > new_dist) {
                    visited[neighbor.first][current.pot - 1] = new_dist;
                    pq.push(Node(neighbor.first, new_dist, current.pot - 1, back_out_temp));
                }
            }
        }
    }

    return -1; 
}