图片.png

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <set>
#include "disjoint-set.hpp"
#include <string>
#include <queue>
using namespace std;

void read_graph(FILE* fptr, unordered_map<int, vector<pair<int, int>>>& adj_list)
{
    int node_cnt;
    fscanf_s(fptr, "%d", &node_cnt);
    for (int i = 0; i < node_cnt; i++)
    {
        int node;
        fscanf_s(fptr, "%d", &node);
        vector<pair<int, int>> empty;
        adj_list[node] = empty;
    }

    int edge_cnt;
    fscanf_s(fptr, "%d", &edge_cnt);
    for (int i = 0; i < edge_cnt; i++)
    {
        int start;
        int end;
        int weight;
        fscanf_s(fptr, "%d%d%d", &start, &end, &weight);
        adj_list[start].push_back({ end, weight });
    }
}

struct Line
{
    int length = INT_MAX;
    int from = -1;
    friend bool operator < (Line a, Line b)
    {
        return a.length > b.length;
    }
};

int main()
{
    unordered_map<int, vector<pair<int, int>>> adj_list;
    std::string input_file = "input.txt";
    FILE* fptr = fopen(input_file.c_str(), "r");

    read_graph(fptr, adj_list);

    int start_idx;
    fscanf_s(fptr, "%d", &start_idx);
    fclose(fptr);

    priority_queue<pair<int, int>> pq;
    pq.push({ start_idx, 0 });

    vector<Line> table;
    for (int i = 0; i <= adj_list.size(); i++)
    {
        Line line;
        table.push_back(line);
    }
    table[start_idx].from = start_idx;
    table[start_idx].length = 0;

    while (!pq.empty())
    {
        auto qit = pq.top();
        pq.pop();
        int cur_idx = qit.first;
        int length = qit.second;

        for (pair<int, int> pit : adj_list[cur_idx])
        {
            int idx = pit.first;
            int weight = pit.second;
            int new_length = length + weight;
            if (new_length < table[idx].length)
            {
                table[idx].length = new_length;
                table[idx].from = cur_idx;
                pq.push({ idx, new_length });
            }
        }
    }

    return 0;
}

7
1
2
3
4
5
6
7
12
1   2   2 
1   4   1
2   4   3
2   5   10
3   1   4
3   6   5
4   3   2
4   6   8
4   7   4
4   5   2
5   7   1
7   6   1
3