http://acm.pku.edu.cn/JudgeOnline/problem?id=1158
Задача: Светофоры
Дорожное движение в городе Дингилвилле устроено необычным образом. В городе есть перекрестки и дороги, которыми эти перекрестки связаны между собой. Любые два перекрестка могут быть связаны не более чем одной дорогой. Не существует дорог, соединяющих один и тот же перекресток с самим собой. Время проезда по дороге в обеих направлениях одинаково. На каждом перекрестке находится один светофор, который в каждый момент времени может быть либо голубым, либо красным. Цвет каждого светофора изменяется периодически: в течение некоторого интервала времени он голубой, а затем, в течение некоторого другого интервала - красный. Движение по дороге между любыми двумя перекрестками разрешено тогда и только тогда, когда светофоры на обоих перекрестках этой дороги имеют один и тот же цвет в момент въезда на на эту дорогу. Если транспортное средство прибывает на перекресток в момент переключения светофора, то его поведение будет определяться новым цветом светофора. Транспортные средства могут находиться в состоянии ожидания на перекрестках. У вас есть карта города, которая показывает:
- время прохождения каждой дороги (целые числа);
- длительность горения каждого цвета для каждого светофора (целые числа);
- начальный цвет и оставшееся время горения этого цвета (целые числа) для каждого цветофора.
Вы должны определить путь между двумя заданными перекрестками, позволяющий транспортному средству проехать от начальноо перекрестка к конечному за минимальное время с момента старта.
Входные данные:
Первая строка содержит два числа:номер начального перекрестка и номер конечного перекрестка.
Вторая строка содержит два числа N, M.
Следующие N строк содержат информацию об N перекрестках. (i+2)-я строка содержит информацию о перекрестке i: Ci, ric, tiB, tiP где Ci ('B' или 'P') - начальный цвет светофора на перекрестке i.
Следующие M строк описывают M дорог. Каждая строка имеет вид: i, j, lij, где i и j - номера перекрестков, которые связывает эта дорога.
Ограничения:
2 <= N <=300, где N - количество перекрестков. Перекрестки нумеруются целыми числами от 1 до N.
1 <=M <=14 000, где M - количество дорог.
1 <= lij <= 100, где lij - время, необходимое для перемещения от перекрестка i до перекрестка j, используя дорогу, которая соединяет перекрестки i и j.
1 <= tic <= 100, где tic - длительность горения цвета c для светофора на перекрестке i. Индекс c принимает значение 'B' для голубого цвета и 'P' для красного.
1 <= ric <= tic, где ric - оставшееся время свечения начального цвета c на перекрестке i.
Выходные данные:
Если путь существует: первая строка должна содержать минимальное время, необходимое для достижения конечного перекрестка из начального.
Если путь не существует, то единственная строка должна содержать только целое число 0.
Пример входных данных:
1 4
4 5
B 2 16 99
P 6 32 13
P 2 87 4
P 38 96 49
1 2 4
1 3 40
2 3 75
2 4 76
3 4 77
Пример выходных данных:
127
Примечание: В оригинальной версии задачи необходимо было также в случае существования пути во второй строке через пробел вывести список перекрестков, который соответствует найденному минимальному пути. Перекрестки следовало выводить в порядке их посещения. Первое число должно быть номером начального перекрестка, последнее - конечного.
Анализ условия и разбор решения:
#include <iostream>
using namespace std;
struct junct_info{
int Ci;
int ric;
int tiB;
int tiP;
int pre;
int time;
};
struct junct{
int time;
int id;
};
junct_info jt[300];
int map[300][300];
int visit[300];
junct* heap;
int heapsize;
int wait( int time, junct_info j1, junct_info j2){
int c1, r1, c2, r2;
int t1, t2;
if ( time < j1.ric ){
c1 = j1.Ci;
r1 = j1.ric - time;}
else {
t1 = ( time - j1.ric ) % ( j1.tiB + j1.tiP );
if ( j1.Ci == 0 ){
if ( t1 < j1.tiP ){
c1 = 1;
r1 = j1.tiP - t1;}
else {
c1 = 0;
r1 = j1.tiP + j1.tiB - t1;}
}
else {
if ( t1 < j1.tiB ) {
c1 = 0;
r1 = j1.tiB - t1;}
else {
c1 = 1;
r1 = j1.tiP + j1.tiB - t1;}
}
}
if ( time < j2.ric ){
c2 = j2.Ci;
r2 = j2.ric - time;}
else {
t2 = ( time - j2.ric ) % ( j2.tiB + j2.tiP );
if ( j2.Ci == 0 ){
if ( t2 < j2.tiP ){
c2 = 1;
r2 = j2.tiP - t2;}
else {
c2 = 0;
r2 = j2.tiP + j2.tiB - t2;}
}
else {
if ( t2 < j2.tiB ){
c2 = 0;
r2 = j2.tiB - t2;}
else {
c2 = 2;
r2 = j2.tiP + j2.tiB - t2;}
}
}
if ( c1 == c2 ) return 0;
else if ( r1 != r2 ) return ( r1 < r2 ) ? r1 : r2;
else if ( c1 == 0 ){
if ( j1.tiP != j2.tiB )
return r1 + (( j1.tiP < j2.tiB ) ? j1.tiP : j2.tiB);
else if ( j1.tiB != j2.tiP )
return r1 + j1.tiP + ( j1.tiB < j2.tiP ) ? j1.tiB : j2.tiP;
else return -1;}
else {
if ( j1.tiB != j2.tiP )
return r1 + ( j1.tiB < j2.tiP ) ? j1.tiB : j2.tiP;
else if ( j1.tiP != j2.tiB )
return r1 + j1.tiB + ( j1.tiP < j2.tiB ) ? j1.tiP : j2.tiB;
else return -1;}
}
void heap_insert( junct j){
int i, c;
i = heapsize;
heapsize++;
while( i > 0 ){
c = ( i - 1 ) / 2;
if ( heap[c].time < j.time ) break;
heap[i].id = heap[c].id;
heap[i].time = heap[c].time;
i = c;}
heap[i].id = j.id;
heap[i].time = j.time;
}
junct heap_delmin(){
int i, c;
junct ret;
ret.id = heap[0].id;
ret.time = heap[0].time;
heapsize--;
i = 0;
while( i < heapsize / 2 ){
c = i * 2 + 1;
if (c + 1 < heapsize && heap[c].time > heap[c+1].time) c++;
if (heap[heapsize].time < heap[c].time) break;
heap[i].id = heap[c].id;
heap[i].time = heap[c].time;
i = c;}
heap[i].id = heap[heapsize].id;
heap[i].time = heap[heapsize].time;
return ret;
}
int main(){
int src, des;
int n, m;
int i, id1, id2, k, d, index;
char c;
junct j, j1;
bool found;
int path[300], pathlen;
cin >> src >> des;
src--;
des--;
cin >> n >> m;
for ( i = 0; i < n; i++){
cin >> c >> jt[i].ric >> jt[i].tiB >> jt[i].tiP;
if ( c == 'B' ) jt[i].Ci = 0;
else jt[i].Ci = 1;
jt[i].pre = -1;
jt[i].time = -1;
visit[i] = 0;}
for ( i = 0; i < n; i++)
for ( k = 0; k < n; k++) map[i][k] = 0;
for ( i = 0; i < m; i++){
cin >> id1 >> id2;
cin >> map[id1-1][id2-1];
map[id2-1][id1-1] = map[id1-1][id2-1];}
heap = new junct[m];
heapsize = 0;
j.id = src;
j.time = jt[src].time = 0;
heap_insert(j);
for ( i = 0; i < n; i++){
found = 0;
while(heapsize > 0){
j = heap_delmin();
if (visit[j.id] == 0){
found = 1;
break;}
}
if ( !found ) break;
if ( j.id == des ) break;
visit[j.id] = 1;
for (k = 0; k < n; k++){
if (visit[k] == 0 && map[k][j.id] != 0){
d = wait( j.time, jt[j.id], jt[k]);
if (d == -1) continue;
if (j.time + d < jt[k].time || jt[k].time == -1){
j1.id = k;
j1.time = j.time + d + map[k][j.id];
jt[k].time = j1.time;
jt[k].pre = j.id;
heap_insert(j1);}
}
}
}
if ( j.id == des ) cout << j.time << endl;
else cout << 0 << endl;
delete[]heap;
}