总共就完整写出来了这一道题

题目大意

• n个点(n<=200)的图，找到当前图最长路径

输入输出

• 输入：[[1,2,5],[1,3,5],[2,3,10]] // 非原数据

• 输出：40

思路

• 写的太紧张了，加上输入输出的处理，想到的就是直接对每个点做bfs，写了个O(N^4)的算法...不过因为数据量这也能过

• 时间复杂度：遍历所有点NO(N)，每个点进行bfsO(N)，其中bfs遍历所有可能的边对，最多n-1+n-2+...+1，O(N^2)，每个点集对又需要O(N),O(N^4)的时间复杂度了

• 用邻接矩阵来存会好得多，但我想的数据量不大赶紧A了..

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 205;
int g[N][N];

vector<int> ps; // point set, 点集, 记录所有当前使用的点, 

int bfs(int st)
{
    queue<PII> q;
    q.push({st, 0});
    int res = 0;

    while(!q.empty())
    {
        auto tmp = q.front();
        q.pop();

        int p = tmp.first, d = tmp.second;
        for(int i = 0; i < ps.size(); i++)
        {
            int end_p = ps[i];

            if(g[p][end_p] != -1)
            {
                q.push({end_p, d + g[p][end_p]});
                res = max(res, d + g[p][end_p]);
            }
        }
    }
    return res;
}

int main()
{
    string s;
    cin>>s;     // 输入时低位在右，高位在左

    // 对数值进行初始化
    int cnt = 0;
    int st, e, dis;                 // st 起始点，e 终点，dis 距离
    int tmp = 0;                    // 暂存数值元素
    bool vis[N];                    // 用于确定哪些点没有被使用
    memset(vis, false, sizeof vis); 
    memset(g, -1, sizeof g);        // 初始化所有的距离

    for(int i = 0; i < s.size(); i++)
    {
        // cnt用于确定是开始点还是end点, isdigit 判断当前位置字符是否为数字
        if(isdigit(s[i]) && cnt == 0)
        {
            tmp = 0;
            while(isdigit(s[i]))     //需要处理多个字符的情况，从左到右读入我们的数
            {
                tmp *= 10;
                tmp += (s[i] - '0');
                i++;
            }
            st = tmp;
            cnt++;
        }
        else if(isdigit(s[i]) && cnt == 1)
        {
            tmp = 0;
            while(isdigit(s[i]))     //需要处理多个字符的情况
            {
                tmp *= 10;
                tmp += (s[i] - '0');
                i++;
            }
            e = tmp;
            cnt++;
        }
        else if(isdigit(s[i]) && cnt == 2)
        {
            cnt = 0;
            tmp = 0;
            while(isdigit(s[i]))     //需要处理多个字符的情况
            {
                tmp *= 10;          
                tmp += (s[i] - '0');
                i++;
            }
            dis = tmp;

            if(!vis[st])
            {
                ps.push_back(st);
                vis[st] = true;
            }

            if(!vis[e])
            {
                ps.push_back(e);
                vis[e] = true;
            }
            g[st][e] = dis;

        }
    }


    int res = 0;
    for(int i = 0; i < ps.size(); i++) // 对所有的点都进行bfs，找到最大的路径
    {
        res = max(res, bfs(ps[i]));
    }
    cout<<res<<endl;

}