竞赛摩托

#include <iostream>
using namespace std;
const int N=2500;
    int p[N];
const int MAXW = 30000;
const int MaxVertexNum = 30;
typedef char VertexType;
int ans=0;
class MGraph
{
public:
    void CreateGraph();
    void ShortestPath_Floyd();
    void Print_Path_Floyd(int v,int w);

private:
    int vertexnum;
    VertexType vertexs[MaxVertexNum];
    int edgenum;
    bool P[MaxVertexNum][MaxVertexNum][MaxVertexNum];
    int D[MaxVertexNum][MaxVertexNum];
    int arcs[MaxVertexNum][MaxVertexNum];
};

void MGraph::CreateGraph()
{
    cin >> vertexnum >> edgenum;
    int x,d;
    cin>>x>>d;
    for(int i=1;i<x;i++){
    cin>>p[i];
    }
    for (int i = 0; i < vertexnum; i++)
        for (int j = 0; j < vertexnum; j++)
            arcs[i][j] = MAXW;

    for (int i = 0; i < edgenum; i++)
    {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        arcs[v1][v2] = w;
    }
}

void MGraph::ShortestPath_Floyd()
{//用Floyd算法求有向图G中各对顶点v和w之间的最短路径P[v][w]及其带权长度D[v][w]

    //若P[v][w][u] = 1，则u是从v到w当前求得的最短路径上的顶点

    for (int v = 0;v<vertexnum;v++)
        for (int w = 0; w < vertexnum; w++)
        {
            D[v][w] = arcs[v][w];
                for (int u = 0; u < vertexnum; u++) P[v][w][u] = 0;
            if (D[v][w] < MAXW)//从v到w有直接路径
            {
                P[v][w][v] = 1;
                P[v][w][w] = 1;
            }
        }
    for (int u = 0;u< vertexnum;u++)
            for (int v = 0;v<vertexnum;v++)
                for (int w = 0; w < vertexnum; w++)
                {
                    if (D[v][u] + D[u][w] < D[v][w])
                    {
                        D[v][w] = D[v][u] + D[u][w];
                        P[v][w][u] = 1;
                    }
                }
}

void MGraph::Print_Path_Floyd(int v, int w)
{

    int i;
    for (i = 0; i < vertexnum; i++)
    if (i != v && i != w && P[v][w][i] == true) break;

    if (i >= vertexnum) {
        ans=ans+arcs[v][w];
        }
        else
        {
            Print_Path_Floyd(v, i);
            Print_Path_Floyd(i, w);
        }
    
}


int main()
{
    MGraph g;
    g.CreateGraph();
    g.ShortestPath_Floyd();
    int v,w;
    g.Print_Path_Floyd(v, w);
    cout<<ans;

}