C++ 笔试题 奇妙旅行

奇妙旅行

描述

小熊住在由n个城镇(城镇编号from 1 to n)组成的国家里,n-1条双向联通的路将这n个城镇相互连接。所以从一个城镇旅行到其他任意一个城镇都是可行的。小熊想要进行一次旅行，它选择一对城镇(u,v)(u ≠ v)，然后选择从u到v的最短路径完成旅行。(注意：(u,v)和(v,u)被认为是不同旅行。)
然而，在小熊的国家里，有2个特殊的城镇，一个叫伦敦(编号x)，一个叫巴黎(编号y)。伦敦是一个被花香萦绕的小镇，巴黎是一个到处都是蜜蜂的小镇。因此，小熊在旅行过程中，如果先经过伦敦，再经过巴黎，他就会遭到蜜蜂的疯狂攻击。
请你帮帮小熊计算出有多少对(u,v)可供选择来完成旅行计划。

输入描述

第一行包含3个整数，n,x,y(1 ≤n≤3000, 1≤x,y≤n , x ≠ y) ，n表示城镇数量，x表示伦敦的编号,y表示巴黎的编号。
接下来n-1行，每行包括两个整数a,b(1≤a,b≤n1≤a,b≤n, a≠b),描述了城镇a和城镇b之间存在一条道路。
输入保证，任意两点都彼此联通（所给的城镇和道路组成了一棵树）。

输出描述

输出有多少对(u,v)可供小熊选择来完成旅行。

样例输入 1

3 1 3
1 2
2 3

样例输出 1

5

样例输入 2

3 1 3
1 2
1 3

样例输出 2

4

提示

第一个example中,小熊有5种选择
(1,2): 他的路线是 1→2
(2,3): 他的路线是 2→3
(3,2): 他的路线是 3→2
(2,1): 他的路线是 2→1
(3,1): 他的路线是 3→2→1
小熊不能选择(1,3)。因为如果它选择这个路线，他会先访问城镇1(伦敦)再访问城镇3(巴黎)，它会遭到蜜蜂的攻击，这会让小熊受伤。

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <iterator>
#include <climits>    // INT_MAX
#include <algorithm>  // min()
#include <iomanip>    // setw()

using namespace std;

// #define UNIT_TEST 
// #define PRINT_PATH_INFO 

// save the shortest Distance information from starting vertex to each vertex 
struct Distance
{
    string path;
    vector<int> pathInfo;
    int    value;
    bool   visit;
    Distance()
    {
        visit = false;
        value = 0;
        path  = "";
    }
};

class Graph_DG
{
private:
    static const int max_weight = numeric_limits<int>::max();  // INT_MAX;
    int      m_vertexLondon;
    int      m_vertexParis;
    int      m_vertexNum;
    int      m_edgeNum;
    int    **m_adjacentMatrix;
    Distance *m_distance;

    string   convertInt2String(int n);
    bool     check_edgeNum_value(int vertexIn, int vertexOut, int weight);

    set<int> m_vertexInSet;
    set<int> m_vertexOutSet;

    void generateGraphDat();
    void createGraph();
    void Dijkstra(int vertex);
    void reinitDistance();

    void printAdjacentMatrix();
    void printPathInfo(int vertexIn) {};

    int getNumOfPathsOfOneVertex(int vertex);

public:
    Graph_DG() {};
    ~Graph_DG();

    int getTotalNumOfPaths();
};

Graph_DG::~Graph_DG()
{
    delete[] m_distance;
    for (int i = 0; i < this->m_vertexNum; i++)
    {
        delete this->m_adjacentMatrix[i];
    }
    delete m_adjacentMatrix;
}

void Graph_DG::generateGraphDat()
{
    int m_vertexNum;
    int m_edgeNum = 0;
    int vertexIn, vertexOut;
    vector<int> vertexs;

    cin >> m_vertexNum >> this->m_vertexLondon >> this->m_vertexParis;

    for (int i = 1; i <= m_vertexNum - 1; i++)
    {
        cin >> vertexIn >> vertexOut;
        vertexs.push_back(vertexIn);
        vertexs.push_back(vertexOut);
        m_edgeNum += 2;
    }

    ofstream out;
    out.open("graph.dat");
    out << m_vertexNum << " " << m_edgeNum << endl;

    for (unsigned int i = 0; i < vertexs.size() - 1; i += 2)
    {
        out << vertexs[i] << " " << vertexs[i + 1] << " " << 1 << endl;
        out << vertexs[i + 1] << " " << vertexs[i] << " " << 1 << endl;
    }
    out.close();
}

bool Graph_DG::check_edgeNum_value(int vertexIn, int vertexOut, int weight)
{
    if (vertexIn < 1 || vertexOut < 1 || vertexIn > m_vertexNum ||
        vertexOut > m_vertexNum || weight < 0)
    {
        return false;
    }
    return true;
}

void Graph_DG::reinitDistance()
{
    delete[] m_distance;

    m_distance = new Distance[this->m_vertexNum];
    for (int i = 0; i < this->m_vertexNum; i++)
    {
        m_distance[i].value = 0;
    }
}

void Graph_DG::createGraph()
{
    int vertexIn;
    int vertexOut;
    int weight;

    ifstream ifp("graph.dat");
    ifp >> this->m_vertexNum >> this->m_edgeNum;

    // allocate space for m_adjacentMatrix and m_distance 
    m_adjacentMatrix = new int*[this->m_vertexNum];
    m_distance = new Distance[this->m_vertexNum];

    for (int i = 0; i < this->m_vertexNum; i++)
    {
        m_adjacentMatrix[i] = new int[this->m_vertexNum];
        for (int k = 0; k < this->m_vertexNum; k++)
        {
            // initialize each element of adjacent matrix 
            m_adjacentMatrix[i][k] = max_weight;
        }
    }

    for (int i = 0; i < this->m_vertexNum; i++)
    {
        m_adjacentMatrix[i][i] = 0;
        m_distance[i].value    = 0;
    }

    for (int i = 0; i < this->m_edgeNum; i++)
    {
        ifp >> vertexIn >> vertexOut >> weight;
        m_vertexInSet.insert(vertexIn);
        m_vertexOutSet.insert(vertexOut);
#ifdef UNIT_TEST
        cout << "V" << vertexIn << " -- " << weight << " --> V" << vertexOut << endl;
#endif
        // assign weight value for vertexIn to vertexOut
        m_adjacentMatrix[vertexIn - 1][vertexOut - 1] = weight;

        // add the following line for undirected graph 
        // m_adjacentMatrix[vertexOut-1][vertexIn-1] = weight;
    }
    ifp.close();
}

void Graph_DG::printAdjacentMatrix()
{
    cout << "Graph's adjacent matrix is " << endl;
    int row = 0;
    int col = 0;

    // start to print adjacent matrix
    for (int row = 0; row < this->m_vertexNum; row++)
    {
        for (int col = 0; col < this->m_vertexNum; col++)
        {
            if (max_weight == m_adjacentMatrix[row][col])
            {
                cout << "∞" << " ";
            }
            else
            {
                cout << setw(2) << m_adjacentMatrix[row][col] << " ";
            }
        }
        cout << endl;
    }
}

string Graph_DG::convertInt2String(int n)
{
    string s;
    stringstream os;
    os << n;
    os >> s;
    return s;
}

void Graph_DG::Dijkstra(int vertex)
{
    // Firstly, initialize distance array 
    for (int vertexIdx = 0; vertexIdx < this->m_vertexNum; vertexIdx++)
    {
        // set the current path
        m_distance[vertexIdx].path = "V" + convertInt2String(vertex)
			+ " --> V" + convertInt2String(vertexIdx + 1);
        m_distance[vertexIdx].value = m_adjacentMatrix[vertex - 1][vertexIdx];
        m_distance[vertexIdx].pathInfo.push_back(vertex);
        m_distance[vertexIdx].pathInfo.push_back(vertexIdx + 1);
    }

    // calculate the shortest distance from vertex to other vertex (this->m_vertexNum-1)
    for (int m_vertexNum = 1; m_vertexNum < this->m_vertexNum; m_vertexNum++)
    {
        int tmpVertex = 0;  // save the minimum vertex index in array m_distance[]
        int min_value = max_weight; // save the minimum value
        for (int vertexIdx = 0; vertexIdx < this->m_vertexNum; vertexIdx++)
        {
            if (!m_distance[vertexIdx].visit && m_distance[vertexIdx].value < min_value)
            {
                min_value = m_distance[vertexIdx].value;
                tmpVertex = vertexIdx;
            }
        }

        // add tmpVertex to shortest distance path information
        m_distance[tmpVertex].visit = true;

        for (int vertexIdx = 0; vertexIdx < this->m_vertexNum; vertexIdx++)
        {
            // the condition m_adjacentMatrix[tmpVertex][i]!=max_weigh is required
            if (!m_distance[vertexIdx].visit && m_adjacentMatrix[tmpVertex][vertexIdx] != max_weight &&
                (m_distance[tmpVertex].value + m_adjacentMatrix[tmpVertex][vertexIdx]) < m_distance[vertexIdx].value)
            {
                //if new edge could impact other vertexs which are not visited, update its distance path information
                m_distance[vertexIdx].value = m_distance[tmpVertex].value + m_adjacentMatrix[tmpVertex][vertexIdx];
                m_distance[vertexIdx].path  = m_distance[tmpVertex].path + " --> V" + convertInt2String(vertexIdx + 1);
                m_distance[vertexIdx].pathInfo = m_distance[tmpVertex].pathInfo;
                m_distance[vertexIdx].pathInfo.push_back(vertexIdx + 1);
            }
        }
    }
}

int Graph_DG::getNumOfPathsOfOneVertex(int vertex)
{
    int  numOfPaths = 0;
    bool foundLondonTown;
    bool foundParisTown;

    for (int i = 0; i != this->m_vertexNum; i++)
    {
        foundLondonTown = false;
        foundParisTown  = false;

        if (m_distance[i].value > 0 && m_distance[i].value != max_weight)
        {
            int size = m_distance[i].pathInfo.size();

            for(int j=0; j<size; j++)
            {
                if (m_distance[i].pathInfo[j] == this->m_vertexLondon)
                {
                    foundLondonTown = true;
                }
                else if (m_distance[i].pathInfo[j] == this->m_vertexParis &&
				     true == foundLondonTown)
                {
                    foundParisTown = true;
                }
            }
            if (false == foundParisTown)
            {
                numOfPaths++;
#ifdef PRINT_PATH_INFO
                for (int j = 0; j < size - 1; j++)
                {
                    cout << m_distance[i].pathInfo[j] << " -> ";
                }
                cout << m_distance[i].pathInfo[size-1] << endl;
#endif
            }
        }
    }
    return numOfPaths;
}

int Graph_DG::getTotalNumOfPaths()
{
    generateGraphDat();  // input data 

    createGraph();

    set<int>::iterator iter;
    int numOfPaths = 0;
    for (iter = m_vertexInSet.begin(); iter != m_vertexInSet.end(); iter++)
    {
        Dijkstra(*iter);

        numOfPaths += getNumOfPathsOfOneVertex(*iter);

        reinitDistance();  // re-initialize distance information
    }

    return numOfPaths;
}

int main()
{
    Graph_DG graph;

    cout << graph.getTotalNumOfPaths() << endl;

    return 0;
}