Самый длинный путь в DAG

Question

Я недавно начал программировать (с C++), и я был представлен на этом сайте под названием UVa OnlineJudge. Это место, где можно представить решения проблем и проверить их на своих серверах. Я начал заниматься некоторыми из их проблем. Но сегодня я столкнулся с проблемой, которую не могу найти.

Проделав самый длинный путь в невзвешенной группе обеспечения доступности баз данных, мне удалось решить все случаи в их режиме отладки. И мне мой код кажется совершенно в порядке. Возможно, это слишком грязно, но это не должно иметь никакого значения. Тем не менее, я получаю отзыв "неправильный ответ" через 0,03 секунды, когда я отправляю свой код.

Я думаю, что это проблемы с памятью / вводом-выводом, но я могу (очень) ошибаться. Любая помощь будет оценена.

Заранее извините, что написал все в main():

//my plan is to use topsort
//locate the starting point in the topological map
//then use a simplified dijkstra algorithm to do the rest

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

class Vertex
{
public:
    int name;
    vector<int> edge;  //outgoing edges
    int weight=0;
    int inc=0;  //number of incoming edges
};


int main()
{
    int n;
    int l=1;
    while(cin>>n&&n!=0)
    {
        //initializing
        vector<Vertex> cities;
        for(int i=0; i<n; i++)
        {
            Vertex c;
            c.name=i;
            cities.push_back(c);
        }

        //reading input
        int start;
        cin>>start;
        start-=1;
        int a, b;
        vector<int> useless;
        while(cin>>a>>b&&a!=0&&b!=0)
        {
            b-=1; //re-index from 0 instead of 1
            a-=1;
            cities[a].edge.push_back(b);  //enlists b as target vertex
            cities[b].inc++;   //adds 1 to b's number of incoming edges
        }


        //topsort
        vector<int> map; //indexes the cities in topological order, starting from 0
        vector<Vertex> S;
        for(auto it : cities) //finds all cities without roads TO them, and puts them in S
        {
            if(it.inc==0)
            {
                S.push_back(it);
            }
        }
        while(S.empty()==false)
        {
            for(auto it : S[0].edge)
            {
                cities[it].inc-=1;
                if(cities[it].inc==0)
                    S.push_back(cities[it]);
            }
            map.push_back(S[0].name);
            S.erase(S.begin());
        }

        /*for(auto it : map)
            cout<<it<<' ';
        cout<<'\n';  //outputs the topological map for checking*/

        int x=0,y; //x is the length of the longest path (yet), and y is the destination of that path. If multiple paths are equally max long, pick the one with smallest y
        int startp=0; //find position of start in the topological map
        for(auto it : map)
        {
            if (it==start)
                break;

            else startp++;
        }

        for(vector<int>::iterator it = map.begin()+startp; it<map.end(); it++)
        {
            //checks if it is record length
            if (cities[*it].weight>x)
            {
                x=cities[*it].weight;
                y=cities[*it].name;
            }
            else if(cities[*it].weight==x)
                if(cities[*it].name<y)
                    y=cities[*it].name;

            //handles its edges
            for(auto itt : cities[*it].edge)
            {
                if(cities[itt].weight<cities[*it].weight+1)
                    cities[itt].weight=cities[*it].weight+1;

            }
        }

        y+=1;
        start+=1;

        cout<<"Case "<<l<<": The longest path from "<<start<<" has length "<<x<<", finishing at "<<y<<'.'<<'\n'<<'\n';
        l++;
    }

    return 0;
}

Answer 1

Я не знаю, почему ваш код не работает, но я подумал, что вам должно быть поучительно показать, что есть гораздо более чистое решение этой проблемы. Простой подход DP решил бы это элегантно. E является вектором, который содержит информацию о ребрах (E [i] является вектором, который содержит список узлов, примыкающих к узлу i). R - это таблица поиска, используемая для того, чтобы не пересчитывать один и тот же самый длинный путь из вершины n снова и снова.

std::pair<int,int> longest(vector<vector<int>>& E, vector<pair<int,int>>& R, int n) {
    if(E[n].size() == 0)
        return make_pair(0,n);

    if(R[n].first != -1)
        return R[n];

    for(auto& e : E[n]) {
        std::pair<int,int> p = longest(E,R,e);
        if(p.first + 1 >  R[n].first || (p.first+1==R[n].first && p.second < R[n].second)) {
            R[n].first = p.first+1;
            R[n].second=p.second;
        }
    }
    return R[n];

}

Полный код здесь. Надеюсь это поможет.