/* ЗАДАЧА А2. СВЕТОФАРИ Както много преспективен млад програмист Мушмурок Мушмулов никога не отказва работа, особено когато тя е добре платена. За негово съжаление обаче крайният срок за задачата, която му е поставена от Двулично Дружеството с Неограничена Безотговорност "Пешо и братчеди", е утре сутринта. Като за капак, той има огромно желание да отиде на концерта на нашумялата рап група "Мързеливи Мушмули". Ето защо се нуждае от вашата помощ. ДДНБ "Пешо и братчеди" е транспортна фирма. До скоро те плащали на шофьорите си почасово, но бързо разбрали, че ако се плаща за превозване на товара от зададена точка в града, до друга зададена точка, това ще мотивира шофьорите да доставят стоките по-бързо и с по-малко разходи за фирмата. За целта е необходима програма, която да избира най-бързия маршрут между зададени две точки. Градът се състои от кръстовища и улици, всяка от които свързва две кръстовища. Кръстовищата са номерирани от 1 до N. За преминаването по всяка улица е необходим определен интервал от време. Задачата се усложнява от факта, че на всяко кръстовище в града е монтиран специален "светофар". Действието на тези устройстава се състои в това, че могат да забавят превозните средства, преминаващи през кръстовището. Светофарите действат по следния начин: За всяко кръстовище, свързаните с него посредством улица кръстовища са разбити в K множества, някои от които може и да са празни: Нека камион прибижава кръстовището X по улицата, която го свързва с кръстовището Y, като междувременно е преминал по S = q*K+R улици (включително улицата X-Y). Ако Y не е от списъка AR, камионът ще бъде забавен, а ако е от списъка AR - ще бъде пропуснат от светофара без забавяне. Забавянето на всеки светофар е зададено и за различните светофари може да бъде различно. Тъй като крайната точка на превоза може да не е от страната от която идва камиона ще считаме, че той изчаква и на крайното кръстовище, ако правилото го изисква. Напишете програма LIGHTS.EXE, която по зададени номера на начално и крайно кръстовище изчислява минималното време необходимо за придвижване между тях. Входните данни се четат от стандартния вход. На първия му ред са зададени 3 цели положителни числа: броят на кръстовищата N (2 <= N <= 200), броят на улиците M и K (1 <= K <= 10). Следват N описания на кръстовища. Първият ред на такова описание съдържа едно положително число - "евентуалното" забавяне причинено от светофара. Следват К реда, всеки съдъжащ номерата на кръстовищата от съответния списък и завършващ с -1. След описанието на кръстовища следват M реда, описващи улиците. Всеки от тези редове съдържа 3 естествени числа - номерата на двете кръстовища, които съответната улица свързва, както и времето за преминаването й. Входните данни завършват със списък от двойки номера, съответно на начално и крайно кръстовище за интересните маршрути, като няма повтарящи се маршрути. Резултатът трябва да се изведе на стандартния изход. За всеки поискан маршрут програмата трябва да изведе един ред с минималното време, необходимо за изминаване на маршрута или низа "No route", ако няма нито един маршрут. ПРИМЕР: Вход: 8 9 2 10 -1 2 3 -1 5 1 3 -1 4 5 -1 5 1 -1 2 4 -1 4 2 3 -1 6 -1 7 2 -1 6 -1 2 4 5 -1 -1 100 8 -1 -1 100 7 -1 -1 1 2 11 1 3 15 2 3 6 2 4 7 2 5 30 3 4 12 4 6 34 5 6 2 7 8 2000 1 6 1 7 Изход: 50 No route Решение на задача А2 - Светофари От Иван Анев За задачи за намиране на най-къс път в граф има няколко известни алгоритми, чието директно прилагане във случая няма да ни дадат вярно решение. В алгоритъма на Дейкстра например разчитаме да намерим най-късия път до даден връх и чрез него да строим къси пътища до неговите съседи. Ако сме намерили къс път до даден връх, на следващата стъпка поради броят на улиците, който сме преминали до момента може да се наложи дълго чакане на светофар, а за друг не чак толкова къс път може да не се налага чакане и така да получим по оптимален вариант от първия. Така се оказва че някои неоптимални на пръв поглед пътища за даден връх дават по-оптимални резултати за други върхове. По-горните разсъждения ни навеждат на мисълта, че освен дължината на пътя, оптималното решение ще зависи от броят на преминатите улици, или по-точно остатъка при деление на K на този брой. Лесно решение на проблема е за всеки връх да пазим не само дължината на най-късия път, а дължината на най-късия път със брой улици, който дава остатък r при деление на K, за всички възможни остатъци. Така на практика се получава нов граф с N*K върха, като за всеки връх от първия граф имаме K нови върха, като във всеки ще влизат само пътища, на които броят на улиците е с определен остатък при деление на K. Ако в първоначалния граф сме имали ребро между a и b, то сега ще имаме K нови ребра, а именно между два представителя на a и b такива, че остатъците на броят на улиците на пътищата, за които отговарят се различава с единица. После ще приложим алгоритъма на Дейкстра във новия граф за всеки начален връх, за който се търси най-къс път, като запазваме резултатите, за да не изчисляваме по два пъти едни и същи неща. А отговора за даден краен връх, ще е най-добрия от всички отговори за неговите представители. */ /* NAME: Ivan Anev PROG: lights LANG: C++ */ #include <cstring> #include <cstdio> using namespace std; const int maxn = 200; const int maxk = 10; const int maxd = 1000000000; class Lights { private: struct Edge { int v, w; Edge *next; }; struct Vex { int slow; Edge *edges; }; private: int n, m, k; Vex vs[maxn]; int s[maxn][maxk][maxn]; int d[maxn][maxn]; int x[maxn*maxk], v[maxn*maxk]; int computed[maxn]; private: void add_edge(int a, int b, int w) { Edge *e; e = new Edge; e->v = b; e->w = w; e->next = vs[a].edges; vs[a].edges = e; } void dijkstra(int src) { int i, j, nn, t, cv, cr, nv, nr, nt, ev; Edge *e; nn = n * k; for (i = 0; i < nn; i++) { v[i] = 0; x[i] = maxd; } x[src*k] = 0; for (i = 0; i < nn; i++) { t = -1; for (j = 0; j < nn; j++) if (v[j] == 0 && (t == -1 || x[j] < x[t])) t = j; v[t] = 1; cv = t / k; cr = t % k; nr = (cr + 1) % k; for (e = vs[cv].edges; e; e = e->next) { nv = e->v; nt = x[t] + e->w; if (s[nv][nr][cv] == 0) nt += vs[nv].slow; ev = nv * k + nr; if (x[ev] > nt) x[ev] = nt; } } for (i = 0; i < n; i++) { t = maxd; for (j = 0; j < k; j++) if (x[i*k+j] < t) t = x[i*k+j]; d[src][i] = t; } } public: void solve() { int i, j, t, a, b, w; scanf("%d%d%d", &n, &m, &k); memset(s, 0, sizeof(s)); for (i = 0; i < n; i++) { scanf("%d", &vs[i].slow); for (j = 0; j < k; j++) while (1) { scanf("%d", &t); if (t == -1) break; s[i][j][t-1] = 1; } } for (i = 0; i < m; i++) { scanf("%d%d%d", &a, &b, &w); add_edge(a - 1, b - 1, w); add_edge(b - 1, a - 1, w); } memset(computed, 0, sizeof(computed)); while (scanf("%d%d", &a, &b) == 2) { a--; b--; if (computed[a] == 0) { dijkstra(a); computed[a] = 1; } if (d[a][b] < maxd) printf("%d\n", d[a][b]); else printf("No route\n"); } } }; Lights lights; int main() { lights.solve(); return 0; }