2014
03-16

# Trip the Lights Fantastic

Bob Roberts (father of Little Bobby of problem D) works at the Traffic Commission for a medium size town. Bob is in charge of monitoring the traffic lights in the city and dispatching repair crews when necessary. Needless to say, Bob has a lot of free time, so to while away the hours he tries to figure out the quickest way to take short trips between various points in the city. Bob has at his disposal a lot of information: the layout of streets in the city and the location and cycle times for all of the traffic lights. To simplify the solution process, he makes the following assumptions:

1. All cars travel at the same top speed, and, if sitting at a red light, take 5 seconds to react and get up to speed. (That is, Bob assumes the car is essentially standing still for 5 seconds, then proceeds at top speed. Bob also assumes the light will not have turned back to red in the 5 seconds it takes to get going.)

2. Each car approaches a light at full speed and either passes through the light if it is green or yellow, or comes to an immediate stop if it is red. Cars are allowed to pass through a light if they hit it just as it is turning to green. Cars must stop if they reach the light just as it is turning to red.

3. The time to make turns through a light is ignored. It is possible to travel between any two lights, although perhaps not directly.

Furthermore, no u-turns are allowed nor will routes revisit an intersection. Even given these assumptions, Bob has difficulty coming up with minimum time paths. Let’s see if you can help him.

The first line of each test case will contain four positive integers n, m, s, and e, where n (2 ≤ n ≤ 100) is the number of traffic lights (numbered 0 through n – 1), m is the number of roads between the traffic lights, and s and e (se) are the starting and ending lights for the desired trip. There will then follow n lines of the form g y r indicating the number of seconds that each light is green, then yellow, then red. (1 ≤ g, y, r ≤ 100.) The first of these lines refers to light 0, the second to light 1, and so on. Following these n lines will be m lines, each describing one road. These lines will have the form l1 l2 t, where l1 and l2 are the two lights being connected by the road and t is the time (in seconds, t ≤ 500) to travel the length of the road at full speed ― you should add 5 to this value to obtain the travel time when driving the road beginning at a standstill. All roads are two way. At time 0, all lights are just starting their green period and your car is considered to be at a standstill at traffic light s. Since it takes 5 seconds to get going, you may assume that g + y is never less than or equal to 5. The last test case is followed by a line containing 0 0 0 0 indicating end-of-input.

The first line of each test case will contain four positive integers n, m, s, and e, where n (2 ≤ n ≤ 100) is the number of traffic lights (numbered 0 through n – 1), m is the number of roads between the traffic lights, and s and e (se) are the starting and ending lights for the desired trip. There will then follow n lines of the form g y r indicating the number of seconds that each light is green, then yellow, then red. (1 ≤ g, y, r ≤ 100.) The first of these lines refers to light 0, the second to light 1, and so on. Following these n lines will be m lines, each describing one road. These lines will have the form l1 l2 t, where l1 and l2 are the two lights being connected by the road and t is the time (in seconds, t ≤ 500) to travel the length of the road at full speed ― you should add 5 to this value to obtain the travel time when driving the road beginning at a standstill. All roads are two way. At time 0, all lights are just starting their green period and your car is considered to be at a standstill at traffic light s. Since it takes 5 seconds to get going, you may assume that g + y is never less than or equal to 5. The last test case is followed by a line containing 0 0 0 0 indicating end-of-input.

3 3 0 2
3 4 5
3 3 3
2 4 4
0 1 1
1 2 2
0 2 12
3 3 0 2
3 4 5
3 4 3
2 4 4
0 1 1
1 2 2
0 2 12
0 0 0 0

0:16
0:08

#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
#define MAXN 150
using namespace std;
int n,m,ids,ide,ans;
int br[MAXN][MAXN],dist[MAXN];
struct Node{
int g,y,r;
}node[MAXN];
struct L{
int  x,t;
bool operator <(L othr)const{
if(x==othr.x)return t<othr.t;
else return x<othr.x;
}
}now;
void SPFA(){
set<L>Q;
Q.clear();
memset(dist,-1,sizeof(dist));
Q.insert((L){ids,5});
dist[ids]=5;
set<L>::iterator  it;
while(!Q.empty()){
it=Q.begin();
now=*it;
Q.erase(it);
for(int i=0;i<n;i++){
if(br[now.x][i]==-1)continue;
nowtime=br[now.x][i]+dist[now.x];
tot=node[i].g+node[i].r+node[i].y;
res=nowtime%tot;
if(i==ide&&(ans==-1||ans>nowtime))ans=nowtime;
Q.insert((L){i,dist[i]});
}
}
}
}
int main(){
while(scanf("%d%d%d%d",&n,&m,&ids,&ide)!=EOF&&(n||m||ids||ide)){
if(ids==ide){
printf("0:00\n");
continue;
}
for(int i=0;i<n;i++){
scanf("%d%d%d",&node[i].g,&node[i].y,&node[i].r);
}
memset(br,-1,sizeof(br));
for(int i=0;i<m;i++){
int  xx,yy,zz;
scanf("%d%d%d",&xx,&yy,&zz);
if(br[xx][yy]==-1||br[xx][yy]>zz)
br[xx][yy]=br[yy][xx]=zz;
}
ans=-1;
SPFA();
int second=ans;
int minute=second/60;
second=second%60;
printf("%d:%02d\n",minute,second);
}
}

1. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3