问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1158思路:
按照Dijkstra算法的思路来求解，关键是每确定一个顶点的更新操作需要考虑因为交通灯导致的等待时间
算法本身并不复杂，自己写出来以后一直TLE...
分析之后的原因是计算两个junctions之间等待交通灯一致所需要等待的时间这一代码块会导致超时
我自己的naive想法是依次递增等待时间(加1)，然后检查交通灯是否一致
去图书馆看书的时候突然想到可以取模，但本质还是递增检查，结果还是TLE
参考了别人代码后发现，在取模之后，就可以分情况讨论，直接得出等待时间
参考:
http://blog.sina.com.cn/s/blog_5c95cb070100cxtr.html代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 301
5 #define INF 0x7FFFFFFF
6 #define Min(a, b) ((a)<(b) ? (a) : (b))
7 struct Junction {
8 int color; /* 0: blue, 1: purple */
9 int left;
10 int dur[2]; /* 0: blue, 1: purple */
11 }junctions[MAX_N];
12 int from, to;
13 int n, m;
14 int adj[MAX_N][MAX_N], d[MAX_N], in[MAX_N];
15
16 void
17 find_color(int index, int past, int *color, int *left) /* past: the time past from 0 */
18 {
19 int i;
20 if(past < junctions[index].left) {
21 *color = junctions[index].color;
22 *left = junctions[index].left - past;
23 return;
24 }
25 past -= junctions[index].left;
26 past = past%(junctions[index].dur[0] + junctions[index].dur[1]);
27 if(junctions[index].color == 0) {
28 if(past<junctions[index].dur[1]) {
29 *color = 1;
30 *left = junctions[index].dur[1] - past;
31 } else {
32 *color = 0;
33 *left = junctions[index].dur[0] + junctions[index].dur[1] - past;
34 }
35 }
36 else {
37 if(past<junctions[index].dur[0]) {
38 *color = 0;
39 *left = junctions[index].dur[0] - past;
40 } else {
41 *color = 1;
42 *left = junctions[index].dur[0] + junctions[index].dur[1] - past;
43 }
44 }
45 }
46
47 void
48 update(int index, int bt) /* bt: the beginning time for current update */
49 {
50 int i, tm, color_a, color_b, left_a, left_b;
51 for(i=1; i<=n; i++) {
52 if(!in[i] && adj[index][i] && d[i]>bt+adj[index][i]) {
53 find_color(index, bt, &color_a, &left_a);
54 find_color(i, bt, &color_b, &left_b);
55 if(color_a == color_b)
56 tm = 0;
57 else {
58 if(left_a != left_b)
59 tm = Min(left_a, left_b);
60 else {
61 if(color_a == 0) {
62 if(junctions[index].dur[1] != junctions[i].dur[0])
63 tm = left_a + Min(junctions[index].dur[1], junctions[i].dur[0]);
64 else if(junctions[index].dur[0] != junctions[i].dur[1])
65 tm = left_a + junctions[index].dur[1] + Min(junctions[index].dur[0], junctions[i].dur[1]);
66 else
67 tm = INF;
68 }
69 else {
70 if(junctions[index].dur[0] != junctions[i].dur[1])
71 tm = left_a + Min(junctions[index].dur[0], junctions[i].dur[1]);
72 else if(junctions[index].dur[1] != junctions[i].dur[0])
73 tm = left_a + junctions[index].dur[0] + Min(junctions[index].dur[1], junctions[i].dur[0]);
74 else
75 tm = INF;
76 }
77 }
78 }
79 if(tm!=INF && d[i]>d[index]+adj[index][i]+tm)
80 d[i] = d[index]+adj[index][i]+tm;
81 }
82 }
83 }
84
85 void
86 dijkstra(int source)
87 {
88 int i, j, k, cur;
89 memset(in, 0, sizeof(in));
90 for(i=1; i<=n; i++)
91 d[i] = INF;
92 in[source] = 1;
93 d[source] = 0;
94 update(source, 0);
95 for(i=2; i<=n; i++) {
96 cur = INF;
97 for(j=1; j<=n; j++)
98 if(!in[j] && d[j]<=cur) {
99 k = j;
100 cur = d[j];
101 }
102 in[k] = 1;
103 if(k == to)
104 break;
105 if(d[k] != INF)
106 update(k, d[k]);
107 }
108 }
109
110 void
111 input_init()
112 {
113 int i, f, t, c;
114 char tmp[2];
115 scanf("%d %d", &n, &m);
116 for(i=1; i<=n; i++) {
117 scanf("%s %d %d %d", tmp, &junctions[i].left, &(junctions[i].dur[0]), &(junctions[i].dur[1]));
118 junctions[i].color = (tmp[0]=='B' ? 0 : 1);
119 }
120 memset(adj, 0, sizeof(adj));
121 for(i=0; i<m; i++) {
122 scanf("%d %d %d", &f, &t, &c);
123 adj[f][t] = c;
124 adj[t][f] = c;
125 }
126 }
127
128 int
129 main(int argc, char **argv)
130 {
131 while(scanf("%d %d", &from, &to) != EOF) {
132 input_init();
133 dijkstra(from);
134 printf("%d\n", d[to]==INF ? 0 : d[to]);
135 }
136 }