sgu 103 Traffic Lights-广搜－优先列队

我是用广搜把这道题过了的，也就是处理等待的时间难一点。我是用一个Deal函数算出在时间T的时刻某个点的颜色，和下个颜色出现还有多少时间还有下下个颜色出现还有多少时间。如果两个点的颜色相同等待时间就为0，否则如果下个颜色出现的时间不同则等待时间为两个点下个颜色出现的时间最小值，否则如果下下个颜色出现的时间不同则等待时间为下下个颜色出现的最小值。

/* ID: mnlm1991 PROG: sgu 103 traffic lights LANG: C++ */ #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<vector> #include<algorithm> #include<string> #include<map> #include<set> #include<bitset> #include<queue> #include<iostream> using namespace std; const int MaxN = 301; int start; int end; struct QNode { int node; int t; vector <int> ans; QNode(int n, int time, vector <int> p):node(n), t(time), ans(p) { } bool operator < (const QNode &other) const { return t > other.t; } }; int N; int M; struct Junction { bool light; int r; int t[2]; }jnc[MaxN]; priority_queue <QNode> q; int visited[MaxN][201]; int path[MaxN][MaxN]; vector <int> p; void Deal(Junction & jtmp, int t, bool & color, int & next1, int & next2) { int tmp = t % (jtmp.t[0] + jtmp.t[1]); color = (tmp < jtmp.r || tmp >= jtmp.r + jtmp.t[!jtmp.light]) ? jtmp.light : !jtmp.light; if (tmp < jtmp.r) { next1 = jtmp.r - tmp; next2 = jtmp.r + jtmp.t[!jtmp.light] - tmp; } else if (tmp < jtmp.r + jtmp.t[!jtmp.light]) { next1 = jtmp.r + jtmp.t[!jtmp.light] - tmp; next2 = jtmp.r + jtmp.t[0]+ jtmp.t[1] - tmp; } else { next1 = jtmp.t[0] + jtmp.t[1] - tmp + jtmp.r; next2 = jtmp.r + jtmp.t[jtmp.light] - tmp; } } int BFS() { while (!q.empty()) { q.pop(); } memset(visited, 0x7f, sizeof(visited)); visited[start][0] = 0; p.clear(); q.push(QNode(start, 0, p)); while (!q.empty()) { QNode m = q.top(); m.ans.push_back(m.node); q.pop(); if (m.node == end) { p = m.ans; return m.t; } bool color; int next1; int next2; Deal(jnc[m.node], m.t, color, next1, next2); int i; for (i = 0; i < N; i++) { if (path[m.node][i]) { bool c; int n1; int n2; Deal(jnc[i], m.t, c, n1, n2); if (color == c) { int tt = m.t + path[m.node][i]; int tmp = tt % (jnc[i].t[0] + jnc[i].t[1]); if (tt < visited[i][tmp]) { visited[i][tmp] = tt; q.push(QNode(i, tt, m.ans)); } } else if (next1 != n1) { int tt = m.t + path[m.node][i] + min(next1, n1); int tmp = tt % (jnc[i].t[0] + jnc[i].t[1]); if (tt < visited[i][tmp]) { visited[i][tmp] = tt; q.push(QNode(i, tt, m.ans)); } } else if (next2 != n2) { int tt = m.t + path[m.node][i] + min(next2, n2); int tmp = tt % (jnc[i].t[0] + jnc[i].t[1]); if (tt < visited[i][tmp]) { visited[i][tmp] = tt; q.push(QNode(i, tt, m.ans)); } } } } } return 0; } int main() { while (scanf("%d%d", &start, &end) != EOF) { start--; end--; scanf("%d%d", &N, &M); int i; for (i = 0; i < N; i++) { char ch; scanf(" %c%d%d%d", &ch, &jnc[i].r, &jnc[i].t[0], &jnc[i].t[1]); if (ch == 'B') { jnc[i].light = 0; } else { jnc[i].light = 1; } } int x, y, z; memset(path, 0, sizeof(path)); for (i = 0; i < M; i++) { scanf("%d%d%d", &x, &y, &z); path[x - 1][y - 1] = path[y - 1][x - 1] = z; } int ttt = BFS(); printf("%d/n", ttt); if (ttt) { for (i = 0; i < p.size() - 1; i++) { printf("%d ", p[i] + 1); } printf("%d/n", p[i] + 1); } } return 0; }