首页 > 代码库 > TRAFFIC LIGHTS POJ 1158
TRAFFIC LIGHTS POJ 1158
题目大意：
在Dingilville 城市安排是一种不同寻常的方式，每个交叉路口有一条道路连接，一条道路最多连接两个不同的交叉路口。每个交叉路口不能连接他自己。道路旅行一端到另一端的时间是相同的，任何一个交叉路口都有一个红绿灯，它在任意时刻只能有红色或者绿色。当且仅当两个交叉路口的灯的颜色一样的时候才允许从一个交叉路口到达另一个交叉路口。如果一辆车到达一个交叉路口的时候这个灯刚好转换，那么它必须考虑这个灯的颜色。允许车辆在交叉路口等待。
给你这个城市的地图如下：
所有道路的通过时间是整数，每个交叉路口的红绿灯转换时间也是整数 并且所有灯光转换的时间也是整数。你的任务是从源点到终点你所行驶的车辆必须找到一个最短的时间到达，也许果有多个你值要输出其中一个就行。
输入数据：
2 <= N <=300 是 N个节点的编号。 编号是从1->N
1 <=M <=14,000 M 是道路的数量
1 <= lij <= 100 从i 到j的距离
1 <= tic <= 100 代表c颜色在节点 i 的持续时间
1 <= ric <= tic 代表颜色c 在节点 i 的剩余时间
第一行两个整数，一个是源点的编号，一个是终点的编号。
第二行包含两个整数。 一个是N， M。
接下来是N行代表是 N个交叉路口。
每行有 Ci, ric, tiB, tiP ， Ci 是 是 ‘B‘ 或者是 ‘P’ 代表红绿灯的最初颜色， ric 代表颜色c剩余的时间， tiP 代表颜色 P 持续的时间， tiB 代表颜色 B 持续的 时间。
接下来是M行代表 从节点 i 到节点 j 的距离是 l
输出：
如果存在从源点到终点的路径那么我们输出所花费的最小时间， 否则输出 0
题目分析：
最短路不说了 SPFA水过， 难点就是判断从一个点到另一个点的时候需要判断两灯是否一样，假如一样 就能走， 否则不能过。
不能过的时候 在那等待， 一直到等到能过的时候再走， 将等待的时间加上就能算出来。
算等待的时间的时候我是暴力水过的， 也就是暴力判断每一秒是否会出现相同的灯， 假如出现了，返回这个点的时间有一点是要注意的， 假如两个点的灯是一样了， 这一秒也是能走的， 就是错在这WA了一天， 最后写了个简单的数据算是水过去了。
下面是代码 + 注释
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 #include <cmath> 8 #include <cstring> 9 using namespace std; 10 #define INF 0xfffffff 11 #define maxn 520 12 struct Point 13 { 14 char color[2];//当前路灯的颜色 1 B 0 P 15 int R; 16 int P;// 颜色 P 持续的时间 17 int B;//颜色 B 持续的时间 18 } P[maxn]; 19 20 struct Edge 21 { 22 int e, w; 23 Edge(int e=0,int w=0) :e(e), w(w) {} 24 }; 25 vector<Edge> G[maxn]; 26 27 bool vis[maxn]; 28 int dist[maxn]; 29 int Star, End; 30 int n, m; 31 char GetColor(Point A, int time)//得到这个时间点 这个红绿灯的颜色 32 { 33 int timeA = time - A.R; 34 35 if(timeA <= 0) 36 return A.color[0]; 37 38 timeA = timeA%(A.B + A.P); 39 40 if(timeA == 0) 41 timeA = A.B + A.P; 42 43 if( A.color[0] == ‘B‘) 44 { 45 if(timeA <= A.P) 46 return ‘P‘; 47 else 48 return ‘B‘; 49 } 50 else 51 { 52 if(timeA <= A.B) 53 return ‘B‘; 54 else 55 return ‘P‘; 56 } 57 58 } 59 int GetTime(Point A, Point B,int time)//得到两点红绿灯相同的时间 60 { 61 if(A.B == B.P && A.P == B.B && A.color[0] != B.color[0] && A.R == B.R )//这是不可能相同的情况 予以排除 62 return INF; 63 64 while(1)//时间向上累加， 一直得到相同为止 65 { 66 time ++;//时间要先 + 1， 因为我传来的时间是我已经用掉过的时间， 所以要判断他的后一秒 67 if(GetColor(A,time) == GetColor(B,time) ) 68 return time-1;//到达这一点的时候是可以走的， 但是这一点不应算在时间花费内， 因为时间还未过 69 } 70 71 } 72 void Spfa()// SPFA不再赘述， 关键是看两个点之间如何走 73 { 74 Edge Pa, Pn; 75 queue<Edge> Q; 76 dist[Star] = 0; 77 Q.push( Edge(Star,0) ); 78 79 while( !Q.empty() ) 80 { 81 Pa = Q.front(); 82 Q.pop(); 83 vis[Pa.e] = false; 84 int len = G[Pa.e].size(); 85 86 for(int i=0; i<len; i++) 87 { 88 Pn = G[Pa.e][i]; 89 90 int time = GetTime(P[Pa.e], P[Pn.e], dist[Pa.e]) + Pn.w;//得到两个灯一样的最短时间 + 路程时间 更新 dist数组 91 92 if(dist[Pn.e] > time) 93 { 94 dist[Pn.e] = time; 95 96 if( !vis[Pn.e] ) 97 { 98 vis[Pn.e] = true; 99 Q.push(Pn);100 }101 }102 }103 }104 }105 void Init()106 {107 for(int i=0; i<=n; i++)108 {109 G[i].clear();110 vis[i] = false;111 dist[i] = INF;112 }113 }114 115 int main()116 {117 118 while(cin >> Star >> End )119 {120 cin >> n >> m;121 122 Init();123 124 for(int i=1; i<=n; i++)125 {126 scanf("%s%d%d%d",P[i].color,&P[i].R,&P[i].B,&P[i].P);127 }128 129 130 for(int i=0; i<m ; i++)131 {132 int a, b, c;133 scanf("%d%d%d",&a,&b,&c);134 135 G[a].push_back( Edge(b,c) );136 G[b].push_back( Edge(a,c) );137 }138 139 Spfa();140 141 if(dist[End] == INF)142 cout << 0 << endl;143 else144 cout << dist[End] << endl;145 }146 return 0;147 }
TRAFFIC LIGHTS POJ 1158