SGU103 解题手记
　　给的图是一个动态的图，边权非负且在发生周期性的变化。要求两点之间的最短路。
　　考虑Dijstra还能不能用。Dijstra的过程是不断将距离源点最近的点加入集合S，直到目标点也被加入S。Dijstra要求随着路径上节点数目的增加，路径长度也相应增加，即不能出现负权边。他的贪心基于这样的考虑：若能尽早到达某个点，就尽早到达，尽早到达这个点时扩展出的经过这个点的路径，比较晚达到这个点时扩展出的经过这个点的路径短。这个题中，边权的变化是有规律的，我发现尽早到达的想法仍然正确。所以Dijstra可以用。
　　下面想想怎么求某一时刻的边权。边权有两个组成部分：一部分是通过这条道路需要的时间，另一部分是在路口等待的时间。给出时刻t，可以求得道路两端的灯的颜色。若颜色相同，则等待时间即为0；若颜色不同，则需等到某一个灯换颜色为止，特殊的，两个灯同时换了颜色，则需要再等某个灯换颜色，如果出现两个灯连续三次同时变换颜色，则这条道路永远无法通行：
　　设某时刻灯A为紫色，灯B为蓝色。第一次同时变色后，灯A为蓝色，灯B为紫色。而后两灯第二次同时变色，说明灯A的蓝色周期与灯B的紫色周期相等。第三次同时变色，说明灯A的紫色周期与灯B的蓝色周期相等。即，两灯颜色变换的总周期相同而相位相反，说明这条道路无法通行了。
　　程序中将用true代表blue，用false代表purple。
　　Submit 1: WA on 3。在处理连续三次同时变色则道路无法通行时出错。我定义在路口等待的时间为-1时表示无法通行，而我在递归处理连续三次同时变色时，居然写了这样的句子：
　　if (flag>3) return -1;
　　if (v1.t==v2.t) return waittime(time+v1.t,a,b,flag+1)+v1.t;
　　没有做特殊判断，直接用-1就加上v1.t，自然返回不了-1了。
　　Submit 2: WA on 3。把Prim的东西混入到Dijstra里了。Prim里有两个集合——树上集和非树上集，Dijstra里的两个集合是路径点集和非路径上点集。这两个集合的维护方式类似，但意义是不同的。
　　程序结构做了一番改变。
　　Submit 3: WA on 2。忘了图是无向的了。
　　Submit 4: WA on 2。Dijstra又写错了。
　　Submit 5: TLE on 5。很可能是iostream造成的。
　　Submit 6: AC。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

#include <cstdio>
#include <algorithm>
using namespace std;
 
struct color
{
    bool c;
    int t;
};
 
struct vertex
{
    int id,arrtime;
    vertex *pre;
    int tB,tP,rC;
    bool initC;
    vertex():arrtime(-1),pre(0){}
    color getcolor(int time);
};
 
color vertex::getcolor(int time)
{
    color r;
    if (time<rC)
    {
        r.c=initC; r.t=rC-time;
    }
    else if (!initC)  ///if initC is purple
    {
        if (r.c=(time-rC)%(tB+tP)<tB) r.t=tB-(time-rC)%(tB+tP);
        else r.t=tB+tP-(time-rC)%(tB+tP);
    }
    else  ///if blue
    {
        if (r.c=(time-rC)%(tB+tP)>=tP) r.t=tB+tP-(time-rC)%(tB+tP);
        else r.t=tP-(time-rC)%(tB+tP);
    }
    return r;
}
 
bool operator <(vertex &a,vertex &b)  ///acturraly this is >
{
    if (a.arrtime>=0 && b.arrtime>=0) return a.arrtime>b.arrtime;
    else return a.arrtime<0;
}
 
int time2go(int time,vertex &a,vertex &b,int flag)
{
    if (flag>3) return -1;
    color v1=a.getcolor(time),v2=b.getcolor(time);
    if (v1.c==v2.c) return time;
    if (v1.t==v2.t) return time2go(time+v1.t,a,b,flag+1);
    return time+min(v1.t,v2.t);
}
 
int map[301][301];
vertex vertexes[301];
bool inpath[301];
 
void printpath(vertex *v)
{
    if (v->pre) printpath(v->pre);
    printf("%d ",v->id);
}
 
void changevalue(int i,int value)
{
    vertexes[i].arrtime=value;
    while (i>1)
        if (vertexes[i>>1]<vertexes[i])
        {
            swap(vertexes[i],vertexes[i>>1]); i>>=1;
        }
        else break;
}
 
int main()
{
    int source,dest,n,m;
    scanf("%d %d %d %d",&source,&dest,&n,&m);
    for (int i(1);i<=n;i++)
    {
        char str[10];
        vertexes[i].id=i;
        scanf("%s %d %d %d",str,&vertexes[i].rC,&vertexes[i].tB,&vertexes[i].tP);
        vertexes[i].initC=(str[0]=='B');
    }
    changevalue(source,0);
    for (int i(1);i<=m;i++)
    {
        int n1,n2,t;
        scanf("%d %d %d",&n1,&n2,&t);
        map[n1][n2]=t; map[n2][n1]=t;
    }
    inpath[source]=true;
    while (!inpath[dest])
    {
        pop_heap(vertexes+1,vertexes+n+1);
        if (vertexes[n].arrtime<0)
        {
            printf("0\n"); return 0;
        }
        inpath[vertexes[n].id]=true;
        for (int i(1);i<n;i++) if (map[vertexes[n].id][vertexes[i].id])
        {
            int t=time2go(vertexes[n].arrtime,vertexes[n],vertexes[i],1);
            if (t>=0 && (vertexes[i].arrtime<0 || t+map[vertexes[n].id][vertexes[i].id]<vertexes[i].arrtime))
            {
                vertexes[i].pre=&vertexes[n];
                changevalue(i,t+map[vertexes[n].id][vertexes[i].id]);
            }
        }
        n--;
    }
    for (int i=1;;i++) if (vertexes[i].id==dest)
    {
        dest=i; break;
    }
    printf("%d\n",vertexes[dest].arrtime);
    printpath(&vertexes[dest]); printf("\n");
    return 0;
}