DataStructureAndAlgorithm/2023209/main.cpp

#include <stdio.h>
#include <queue>
#include <functional>

struct Point {
    unsigned short name;
    int known_shortest;
    int time;

    Point(int _name, int _known_shortest, int _time): name(_name), known_shortest(_known_shortest), time(_time) {}

    Point() {};
};

template <class T>
struct compare_point {
    bool operator()(T &a, T &b) {
        return a.known_shortest < b.known_shortest;
    }
};
struct Edge{
    unsigned short end, time, cost;
};

int N, M;
unsigned short edges[1050000][3] = {0};
// 边是否顺序？ 按开始点排序
// 时间限制最大是多少？ 超过unsigned short
int head[66000] = {0};
unsigned short start = 0, terminal = 0;
int time_limit = 0;
int path[1000] = {0};
int current_cheap = 2147483647;
Edge edges_dij[1050000] = {0};
bool included[66000] = {0};
Point points[66000];

int dfs(unsigned short cur, int cur_time, int cur_cost, int path_ptr) {
    path[path_ptr] = cur;
    if (cur_time > time_limit) {
        return 0;
    }

    if (cur_cost > current_cheap) {
        return 0;
    }

    if (cur == terminal) {
        if (cur_cost < current_cheap) {
            current_cheap = cur_cost;
        }
        return 0;
    }

    for (int i = head[cur]; i < head[cur + 1]; i++) {
        for (int j = 0; j < path_ptr; j++) {
            if (path[j] == edges[i][0]) {
                continue;
            }
        }
        dfs(edges[i][0], cur_time + edges[i][1], cur_cost + edges[i][2], path_ptr + 1);
    }
    return 0;
}


int dijkstra() {
    std::priority_queue<Point, std::vector<Point>, compare_point<Point>> q;
    for (int i = 0; i < N; i++) {
        points[i] = Point{(unsigned short) i, 2147483647, 2147483647};
        // q.push(points[i]);
    }



    // points[start].known_shortest = 0;
    q.emplace(start, 0, 0);

    while (!q.empty()) {
        Point current = q.top();
        q.pop();
        if (current.name == terminal) {
            printf("%d\n", current.known_shortest);
            break;
        }
        for (int i = head[current.name]; i < head[current.name + 1]; i++) {
            int new_time = current.time + edges_dij[i].time;
            int new_cost = current.known_shortest + edges_dij[i].cost;
            if (new_time > time_limit) {
                continue;
            }
            if (new_cost < points[edges_dij[i].end].known_shortest) {
                q.emplace(edges_dij[i].end, new_cost, new_time);
                points[edges_dij[i].end].known_shortest = new_cost;
                points[edges_dij[i].end].time = new_time < points[edges_dij[i].end].time ? new_time : points[edges_dij[i].end].time;
            }
            else if (new_time < points[edges_dij[i].end].time) {
                q.emplace(edges_dij[i].end, new_cost, new_time);
                points[edges_dij[i].end].time = new_time;
            }
        }
    }

}

int main() {
    scanf("%d %d", &N, &M);
    if (N < 50000) {
        head[0] = 0;
        int next_empty_edge = 0;
        int current_start = 0;
        for (int i = 0; i < M; i++) {
            int from, to, time, cost;
            scanf("%d %d %d %d", &from, &to, &time, &cost);
            if (from != current_start) {
                for (int j = current_start + 1; j <= from; j++) {
                    head[j] = next_empty_edge;
                }
                current_start = from;
                // head[from] = next_empty_edge;
            }
            edges[next_empty_edge][0] = to;
            edges[next_empty_edge][1] = time;
            edges[next_empty_edge][2] = cost;
            next_empty_edge++;
        }
        head[++current_start] = next_empty_edge;
        scanf("%hu %hu %d", &start, &terminal, &time_limit);

        dfs(start, 0, 0, 0);
        if (current_cheap == 2147483647) {
            printf("-1\n");
            return 0;
        }
        printf("%d\n", current_cheap);
        return 0;
    }
    else {
        head[0] = 0;
        int next_empty_edge = 0;
        int current_start = 0;
        for (int i = 0; i < M; i++) {
            unsigned short from, to, time, cost;
            scanf("%hu %hu %hu %hu", &from, &to, &time, &cost);
            if (from != current_start) {
                for (int j = current_start + 1; j <= from; j++) {
                    head[j] = next_empty_edge;
                }
                current_start = from;
                // head[from] = next_empty_edge;
            }
            // edges[next_empty_edge][0] = to;
            // edges[next_empty_edge][1] = time;
            // edges[next_empty_edge][2] = cost;
            edges_dij[next_empty_edge] = Edge{to, time, cost};
            next_empty_edge++;
        }
        head[++current_start] = next_empty_edge;
        scanf("%hu %hu %d", &start, &terminal, &time_limit);

        dijkstra();
        return 0;
    }
}