2009年12月4日星期五.sgu103==pku1158
sgu103:dijkstra
最好自己琢磨以下怎么做
动态dijkstra
trick:
注意两个顶点之间虽然有可能有路，但是由于信号灯的周期有可能永远也不通
sgu上不仅要数出最短路的值还要求输出这条路径。
1
2 const int N = 320;
3 const int inf = 1 << 30;
4 int g[N][N];
5 struct color{
6 int t,c;
7 color(){}
8 };
9 const int BLUE = 1;
10 const int PURPLE = 0;
11 struct node {
12 bool isblue;
13 int tb,tp,rt;
14 node() {}
15 color getColor(int time);
16 }jun[N];
17
18 color node::getColor(int time)
19 {
20 color ret;
21 if(time < rt) {
22 ret.c = isblue;
23 ret.t = rt - time;
24 }else {
25 int cycle = tb + tp;
26 time = (time - rt) % cycle;
27 if(isblue) {
28 if(time < tp) {
29 ret.c = PURPLE;
30 ret.t = tp - time;
31 }else {
32 ret.c = BLUE;
33 ret.t = cycle - time;
34 }
35 }else {
36 if(time < tb) {
37 ret.c = BLUE;
38 ret.t = tb - time;
39 }else {
40 ret.c = PURPLE;
41 ret.t = cycle - time;
42 }
43 }
44 }
45 return ret;
46 }
47
48 int src,dest,m,n,dis[N],pre[N],out[N],top;
49 bool vis[N];
50
51 int time2go(int i,int j,int now,int cnt)
52 {
53 if(cnt > 3) { return inf;}
54 color c1 = jun[i].getColor(now);
55 color c2 = jun[j].getColor(now);
56 if(c1.c == c2.c) {
57 return now;
58 }
59 if(c1.t == c2.t) {
60 return time2go(i,j,now + c1.t,cnt+1);
61 }
62 return now + min(c1.t,c2.t);
63 }
64
65 bool dijkstra()
66 {
67 int i,j,k;
68 memset(vis,0,sizeof(vis));
69 memset(pre,0,sizeof(pre));
70 for(i = 1;i <= n;i++) {
71 dis[i] = inf;
72 }
73 dis[src] = 0;
74 for(k = 1;k <= n;k++) {
75 int idx = 0,val = inf;
76 for(i = 1;i <= n;i++) {
77 if(dis[i] < val && vis[i] == 0) {
78 val = dis[i],idx = i;
79 }
80 }
81 if(idx == 0) {
82 return false;
83 }
84 vis[idx] = 1;
85 for(i = 1;i <= n;i++) {
86 if(vis[i] == false && g[idx][i] < inf){
87 int tmp =time2go(idx,i,dis[idx],0);
88 if(tmp < inf) {
89 int wei =tmp + g[idx][i];
90 if (dis[i] > wei) {
91 dis[i] = wei;
92 pre[i] = idx;
93 }
94 }
95 }
96 }
97 }
98
99 if(dis[dest] >= inf) {
100 return false;
101 }else {
102 printf("%d\n",dis[dest]); top = 0;
103 int tmp = dest;
104 while(tmp > 0) {
105 out[top++] = tmp;
106 tmp = pre[tmp];
107 }
108 for(i = top - 1;i > 0;i--) {
109 printf("%d ",out[i]);
110 }
111 printf("%d\n",out[0]);
112 }
113 return true;
114 }
115
116 int main()
117 {
118 int i,j,k;
119 char s[16];
120 scanf("%d%d",&src,&dest);
121 scanf("%d%d",&n,&m);
122 for(i = 1;i <= n;i++) {
123 scanf("%s %d %d %d\n",s,&jun[i].rt,&jun[i].tb,&jun[i].tp);
124 jun[i].isblue = (s[0] == 'B');
125 }
126 for(i = 1;i <= n;i++) {
127 for(j = 1;j <= n;j++) {
128 g[i][j] = inf;
129 }
130 }
131 for(i = 0;i < m;i++) {
132 int a,b,c;
133 scanf("%d%d%d",&a,&b,&c);
134 g[a][b] = g[b][a] = c;
135 }
136 if(dijkstra() == false) {
137 printf("0\n");
138 }
139 return 0;
140 }
141