Leghosszabb út keresése

Címkék
Leghosszabb út keresése
2004-10-22T23:40:22+02:00
2004-10-24T12:03:23+02:00
2022-10-22T12:25:43+02:00
diego2002
Egy hosszú vasútvonal mentén n város helyezkedik el, minden városnak pontosan egy vasútállomása van a
vonalon. Ismerjük a vonalon közlekedő vonatokat. Minden vonat adott i-edik városból indul és adott j-edik
városba közlekedik (i < j) és közben nem áll meg egyetlen közbülső állomáson sem. Az 1. városból indulva,
vonattal közlekedve a lehető legtöbb várost szeretnénk meglátogatni.
Írjon olyan programot, amely kiszámít egy olyan útvonalat, amelyen közlekedve a lehető legtöbb városba
eljutunk!
Bemeneti specifikáció
A feladat.be szöveges állomány első sora a városok n (1<= n <=1000) számát, és a járatok m (1 < m < 1000)
számát tartalmazza egy szóközzel elválasztva. A további m sor mindegyike két egész számot tartalmaz (egy
szóközzel elválasztva), az első szám i, a járat indulási, a második szám j a járat érkezési állomása (1 <= i < j <= n).
Az állomány i + 1-edik sora az i-edik járat adatát tartalmazza.
Kimeneti specifikáció
A feladat.ki szöveges állomány első sora az útvonal járatainak k számát tartalmazza. A második sor pontosan
k számot tartalmazzon (egy-egy szóközzel elválasztva), a járatok bemenet beli sorszámait az utazás sorrendjében.

feladat.be
5 7
1 2
1 3
2 4
3 5
3 2
3 4
4 5

feladat.ki
4
2 5 3 7

Hát ez lenne a feladat! :)

Megmondom őszintén, hogy én készítettem már egy programot, de nem fordul le gnu alatt, ezért ha valaki tudna egy jó megoldást a feladatra, akkor bátran írjon!

Köszönöm
Mutasd a teljes hozzászólást!
1. itt találod meg az algoritmus, amelyiket egy kicsit átpofozva felhasználhatsz

2. Mit gondolsz, mi a lótúrónak van a beíróablakban a "forráskód" gomb?
Mutasd a teljes hozzászólást!

  • Kersed meg a leghosszab részsorozat lefedése c. topicot, pontosan a te problémád. Még programot is találsz ott, csak a >< relációk helyett = kell.
    Mutasd a teljes hozzászólást!
  • én készítettem már egy programot, de nem fordul le gnu alatt,


    Ezekszerint neked nem megoldás kell, hanem C leckék? Mert ha van programod, akkor gondolom van megoldásod is (algoritmus).
    Nyomd be ide a kódodat, majd gnu-sítjuk neked, és akkor a végén a saját algoritmusod marad benne.
    Mutasd a teljes hozzászólást!
  • Na már sikerült elérnem, hogy leforduljon, és működik is!

    Az gondolom egyértelmű, hogy ez egy kötprog. Viszont, beküldés után egy gép 18 tesztet futtat le rajta, azonban mind a 18-ra ugyanaz a hiba jön ki:

    11. Illegális memória hivatkozás. Az ok vagy hibás indexelés, vagy memórialimit túllépés.

    Ezt kellene kiküszöbölni! Íme a forráskódom!

    #include <iostream>
    #include <fstream>
    using namespace std;

    struct ut{
    int ki;
    int be;
    };

    int melysegMeghatarozas(int kiindulasiPont, int utvonalak[],ut osszesUt[],int vSzama,int jSzama){
    int x=0;
    int melyseg=0;
    for (int a=0;a<jSzama;a++) {
    if (osszesUt[a].be==kiindulasiPont) {
    x++;
    if (osszesUt[a].ki!=vSzama) {
    x=x+melysegMeghatarozas(osszesUt[a].ki, utvonalak, osszesUt, vSzama, jSzama);
    }
    }
    if (x>melyseg) {
    melyseg=x;
    utvonalak[melyseg-1]=a+1;
    }
    x=0;
    }
    return melyseg;
    }

    int main(){
    fstream file_be;
    fstream file_ki;
    file_be.open ("feladat.be", fstream::in);
    file_ki.open ("feladat.ki", fstream::out);
    char sor[10];
    char *egy_sor;
    int i=0;
    int varosok_szama;
    int jaratok_szama;
    file_be.getline(sor,10);
    egy_sor=strtok(sor," ");
    varosok_szama=atoi(egy_sor);
    egy_sor=strtok(NULL," ");
    jaratok_szama=atoi(egy_sor);
    ut *utak=new ut[jaratok_szama];
    while (!(file_be.eof())) {
    file_be.getline(sor,10);
    egy_sor=strtok(sor," ");
    utak.be=atoi(egy_sor);
    egy_sor=strtok(NULL," ");
    utak
    .ki=atoi(egy_sor);
    i++;
    }
    int z;
    int *eredmeny=new int[varosok_szama];
    z=melysegMeghatarozas(1,eredmeny,utak,varosok_szama,jaratok_szama);
    file_ki<<z<<endl;
    for (int u=z-1; u>=0; u--) file_ki<<eredmeny<<" ";
    return 0;
    }
    Mutasd a teljes hozzászólást!
  • 1. itt találod meg az algoritmus, amelyiket egy kicsit átpofozva felhasználhatsz

    2. Mit gondolsz, mi a lótúrónak van a beíróablakban a "forráskód" gomb?
    Mutasd a teljes hozzászólást!
  • Bocs, láttam, hogy ott van de nem használtam!
    Mutasd a teljes hozzászólást!
Címkék
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd