2017年csp测试的第四题，遇到了一些问题，求解答

#具体题目#

#问题描述#
在做2017年csp测试第四题的题目如上图，我感觉是一个比较简单的狄克斯特拉最短路径的变形，我的方法实在原有算法所所维护的每个点的最短距离后加一项“最近连续的小路路径”就是代码中的“dis_table[n][2]_”用这种方法来处理小路相交的问题，但是最后得分为60分，代码应该是完全反应逻辑的了，目前没发现问题，由于csp不能看自己的错误，希望大牛解答

#我的代码#

-----c++



#include<iostream>
#include<vector>

using namespace std;

struct Road
{
    int road_type;
    int to_node;
    int distance;
};

struct Node
{
    int itself;
    vector<Road> neighbours;
};

int **dis_table;
int node_num = 0, road_num = 0;
vector<Node> map;

void Input_ini()
{
    cin >> node_num >> road_num;
    for (int n = 0; n < node_num; n++)
    {
        Node tem;
        tem.itself = n;

        map.push_back(tem);
    }

    for (int n = 0; n < road_num; n++)
    {
        int tem1, tem2, tem3, tem4;
        cin >> tem1 >> tem2 >> tem3 >> tem4;

        Road r1, r2;
        r1.road_type = tem1; r1.to_node = tem3-1; r1.distance = tem4;
        r2.road_type = tem1; r2.to_node = tem2-1; r2.distance = tem4;

        map[tem2 - 1].neighbours.push_back(r1);
        map[tem3 - 1].neighbours.push_back(r2);
    }

    //initial
    dis_table = new int*[node_num];
    for (int n = 0; n < node_num; n++)
    {
        dis_table[n] = new int[3];
        dis_table[n][0] = 1000000;
        dis_table[n][1] = 0;
        dis_table[n][2] = 0;
    }
}

int Find_min()
{
    int min = 1000000;
    for (int n = 0; n < node_num; n++)
    {
        if (dis_table[n][0] < min && dis_table[n][2] == 0)
        {
            min = n;
        }
    }

    return min;
}

int Dijsktra()
{
    int update_num = node_num;
    dis_table[0][0] = 0;

    int result = 0;

    while (update_num>0)
    {
        int index = Find_min();
        if (index == node_num-1)
        {
            //cout << "hhhhhhhhh";
            result = dis_table[index][0];
            break;
        }

        for (int n = 0; n < map[index].neighbours.size(); n++)
        {
            if (dis_table[map[index].neighbours[n].to_node][2] == 1)
                continue;
            else
            {
                if (map[index].neighbours[n].road_type == 0 &&
                    dis_table[index][0] + map[index].neighbours[n].distance < dis_table[map[index].neighbours[n].to_node][0])
                {
                    dis_table[map[index].neighbours[n].to_node][0] = dis_table[index][0] + map[index].neighbours[n].distance;
                    dis_table[map[index].neighbours[n].to_node][1] = 0;
                }
                else if (map[index].neighbours[n].road_type == 1 &&
                    dis_table[index][0] - (dis_table[index][1] * dis_table[index][1]) +
                    ((dis_table[index][1] + map[index].neighbours[n].distance)*(dis_table[index][1] + map[index].neighbours[n].distance)) < dis_table[map[index].neighbours[n].to_node][0])
                {
                    dis_table[map[index].neighbours[n].to_node][0] =

                        dis_table[index][0] - (dis_table[index][1] * dis_table[index][1]) +
                        ((dis_table[index][1] + map[index].neighbours[n].distance)*(dis_table[index][1] + map[index].neighbours[n].distance));

                    dis_table[map[index].neighbours[n].to_node][1] += map[index].neighbours[n].distance;
                }
            }
        }

        dis_table[index][2] = 1;
        update_num--;




/*      for (int n = 0; n < node_num; n++)
        {
            cout << dis_table[n][0] << ' ' << dis_table[n][1] << ' ' << dis_table[n][2] << '\n';
        }
        cout << "\n\n";*/

    }




    return result;
}

int main()
{
    Input_ini();
    cout << Dijsktra();

    return 0;
}

https://blog.csdn.net/qq_26658823/article/details/78145560