#include <cstddef>

#include <iostream>

#include <sstream>

#include <string>

#include <array>

#include <memory>

#include <map>

#include <stack>

#include <vector>

using namespace std;

//控制臺輸入參數 頂點序列，和邊權值

//a b c d e q 空格結束

//ab5 ae4 ac3 bc2 cd8 ce6 de10 q 空格結束

constexpr int MAX_COST = 9999;

union VexItem

{

? ? char value_;

? ? int index_;

};

class Vex

{

public:

? ? Vex(Vex&&) = default;

? ? Vex& operator =(Vex&&) = default;

? ? Vex() = default;

? ? explicit Vex(char ch, int cost = 0)

? ? : cost_(cost)

? ? , rudu_(0)

? ? , next_(nullptr)

? ? {

? ? ? ? vex_item_.value_ = ch;

? ? ? ? //cout << "init vex_item_.value_: " << vex_item_.value_ << endl;

? ? }

? ? explicit Vex(int index, int cost = 0)

? ? : cost_(cost)

? ? , rudu_(0)

? ? , next_(nullptr)

? ? {

? ? ? ? vex_item_.index_ = index;

? ? ? ? //cout << "init vex_item_.index_: " << vex_item_.index_ << endl;

? ? }

? ? VexItem vex_item_;

? ? int cost_;

? ? int rudu_;

? ? shared_ptr<Vex> next_;

};

int main() {

? ? constexpr int input_len{2 + 10};

? ? constexpr auto vex_len{100};

? ? int vex_count{0};

? ? array<Vex, vex_len> vex;

? ? map<char, int> vex_index;

? ? auto string2num = [](const char* str)

? ? {

? ? ? ? int cost{0};

? ? ? ? stringstream ss;

? ? ? ? ss << str;

? ? ? ? ss >> cost;

? ? ? ? return cost;

? ? };

? ? cout << "input vex point" << endl;

? ? for(int i = 0 ;; ++i)

? ? {

? ? ? ? array<char, input_len> input;

? ? ? ? cin.getline(input.data(), input_len, ' ');

? ? ? ? //cout << "you input vex point:" << input.data() << endl;

? ? ? ? if(input[0] == 'q')

? ? ? ? ? ? break;

? ? ? ?

? ? ? ? vex[i] = Vex(input[0]);

? ? ? ? vex_index[input[0]] = i;

? ? ? ? vex_count++;

? ? ? ? //cout << input[0] << " map to " << i << endl;

? ? }

? ? cin.ignore(std::numeric_limits< streamsize >::max(), '\n');

? ? cout << "input vex pair and cost" << endl;

? ? do

? ? {

? ? ? ? array<char, input_len> input;

? ? ? ? cin.getline(input.data(), input_len, ' ');

? ? ? ? //cout << "you input vex pair and cost:" << input.data() << endl;

? ? ? ? if(input[0] == 'q')

? ? ? ? ? ? break;

? ? ? ?

? ? ? ? //cout << input[0] << "}}" << input[1] << endl;

? ? ? ? auto from_index = vex_index[input[0]];

? ? ? ? auto to_idnex = vex_index[input[1]];

? ? ? ? auto tmp = make_shared<Vex>(to_idnex, string2num(input.data() + 2));

? ? ? ?

? ? ? ? tmp->next_ = vex[from_index].next_;

? ? ? ? vex[from_index].next_ = tmp;

? ? ? ? vex[to_idnex].rudu_++;

? ? ? ?

? ? }while(true);

? ? //a b c d e q

? ? //ab5 ae4 ac3 bc2 cd8 ce6 de10 q

? ? stack<int> stack_vex;

? ? vector<int> order_vex;

? ? for(int i = 0; i < vex_count; i++)

? ? {

? ? ? ? auto& item = vex[i];

? ? ? ? if(item.vex_item_.value_ == '\0' && item.vex_item_.index_ == 0)

? ? ? ? ? ? break;

? ? ? ? auto ptr = item.next_;

? ? ? ? cout << "vex :" << item.vex_item_.value_ << ", rudu:" << item.rudu_ << endl;

? ? ? ? if(ptr == nullptr)

? ? ? ? {

? ? ? ? ? ? cout << "end vex:" << item.vex_item_.value_ << endl;

? ? ? ? }

? ? ? ? for(; ptr != nullptr; ptr = ptr->next_)

? ? ? ? {

? ? ? ? ? ? cout << item.vex_item_.value_ << "-" << ptr->cost_ << "->"

? ? ? ? ? ? ? ? ?<< vex[ptr->vex_item_.index_].vex_item_.value_ << " ?";

? ? ? ? }

? ? ? ? cout << endl;

? ?

? ? ? ? if(item.rudu_ == 0)

? ? ? ? {

? ? ? ? ? ? stack_vex.push(i);

? ? ? ? } ? ?

? ? }

? ? while(!stack_vex.empty()) ? ?

? ? {

? ? ? ? auto i = stack_vex.top();

? ? ? ? stack_vex.pop();

? ? ? ? order_vex.push_back(i);

? ? ? ? auto ptr = vex[i].next_;

? ? ? ? for(;ptr != nullptr; ptr = ptr->next_)

? ? ? ? {

? ? ? ? ? ? auto to_index = ptr->vex_item_.index_;

? ? ? ? ? ? vex[to_index].rudu_--;

? ? ? ? ? ? if(vex[to_index].rudu_ == 0)

? ? ? ? ? ? {

? ? ? ? ? ? ? ? stack_vex.push(to_index);

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? cout << "order_vex: " ;

? ? for(auto& itme : order_vex)

? ? {

? ? ? ? cout << vex[itme].vex_item_.value_ << " " ;

? ? }

? ? cout << endl;

? ? //求order_vex 第一個頂點到最后一個頂點的最短路徑

? ? int order_vex_len = order_vex.size();

? ? const int start_vex = 1, end_vex = ?order_vex.back(); //指定路徑前迄點

? ? vector<int> cost(order_vex_len, MAX_COST);

? ? vector<int> succ(order_vex_len, -1);

? ? cost[end_vex] = 0;

? ? int cur_vex_index = 0;

? ? for(int i = 0; i < order_vex_len; ++i)

? ? {

? ? ? ? if(order_vex[i] == end_vex)

? ? ? ? ? ? cur_vex_index = i;

? ? }

? ? while(order_vex[cur_vex_index] != start_vex)

? ? {

? ? ? ? int front_vex = order_vex[--cur_vex_index];

? ? ? ? int front_vex_cost = MAX_COST;

? ? ? ? int front_vex_succ = -1;

? ? ? ? for(int i = 0; i < vex_count; ++i)

? ? ? ? {

? ? ? ? ? ? auto next = vex[front_vex].next_;

? ? ? ? ? ? while(next != nullptr)

? ? ? ? ? ? {

? ? ? ? ? ? ? ? if(next->vex_item_.index_ == i && ?cost[i] + next->cost_ < front_vex_cost)

? ? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? ? front_vex_cost = cost[i] + next->cost_;

? ? ? ? ? ? ? ? ? ? front_vex_succ = i;

? ? ? ? ? ? ? ? ? ? //cout << cur_vex_index << " " << front_vex_cost << " " << front_vex_succ << endl;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? next = next->next_;

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? cost[front_vex] = front_vex_cost;

? ? ? ? succ[front_vex] = front_vex_succ;

? ? }

? ? int path_index = start_vex;

? ? cout << vex[start_vex].vex_item_.value_ << " to " << vex[end_vex].vex_item_.value_

? ? ? ? ?<< " succ path is :" ?<< endl << vex[start_vex].vex_item_.value_ << " ";

? ? do

? ? {

? ? ? ? cout << vex[path_index = succ[path_index]].vex_item_.value_ << " ";

? ? }while(path_index != end_vex);

? ? return 1;

}