题意
http://www.nocow.cn/index.php/Translate:Sgu/103
翻译版，这里不重复劳动了
思路
这个题的可怕之处不是有多难想，而是虽然基本模型很简单就是图上最短路，但是这回有许多许多的限制条件。
正确地计算当前灯的状态是这个题最大的难点，我采用的方法是（其实我写跪了，李大神给我捞上来的）：首先把到这个路口已经消耗的时间减去题目给的初始时间，我叫他有效时间，接下来把这个有效时间模上两种颜色的灯持续时间之和，剩下的时间是对灯的状态真正有影响的时间，接下来分别脑内模拟一下站在这个路灯时如果是紫色最后会怎么变，如果是蓝色会怎么变，然后基本就可以写出这个时间和最终颜色的关系了，还可以得到最终这个颜色还能再持续多长时间，这两条非常重要，一定要搞对。
接下来的难点就是计算从当前点移动到下一个点之前等待两点灯的颜色同步的时间，算这个就要依赖于上面的两个值：当前颜色和当前颜色还剩多长时间，假设我们要从A点移动到B，已经走了tim时间，那么我们就要分别计算A点和B点在tim时的这两个数据，然后如果AB在tim时颜色正好相等，那么无需等待直接通行，所以等待时间为0，如果颜色不同呢？只要看A和B哪个剩余的时间短，这个就是等待时间了。要是剩余的时间又一样？那就要脑内模拟一下了，然后发现我们可以再比较A的下一颜色和B的下一颜色谁的持续时间短，等待时间就是剩余时间＋最短的持续时间。如果下一个颜色还一样，那就比较下下个颜色。要是还一样？对不起，hehe了，走别的吧～（所以说这个题很sxbk)
接下来是最段路部分，我们把权值设定为走到这个点要花多少时间，从当前点走到下一个点时，下一个点的可能值就是(当前点已用时间+等待两个点的灯同步的时间+路上消耗的时间)，以此为基准进行松弛操作。
接下来上代码
|
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 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; int str = 0,ter = 0; int n = 0,m = 0; struct edgeType{ int to; int cost; edgeType(){ to = 0; cost = 0; } edgeType(int ito,int icost){ to = ito; cost = icost; } }; struct vertexType{ char color; int init; int blue; int purple; int pre;//for backtracking int dis; vector<edgeType> edge; vertexType(){ color = 0; init = 0; blue = 0; purple = 0; pre = 0; dis = 0x3f3f3f3f; edge.clear(); } } vertex[305]; char getColor(int timepast,int a){ vertexType &av = vertex[a]; int atime = (timepast % (av.blue+av.purple)) - av.init; if (av.color == 'P') { if (atime < 0) { return 'P'; }else if(atime < av.blue){ return 'B'; }else{ return 'P'; } }else{ if (atime < 0) { return 'B'; }else if(atime < av.purple){ return 'P'; }else{ return 'B'; } } } char getTime(int timepast,int a){ vertexType &av = vertex[a]; int atime = (timepast %(av.blue+av.purple)) - av.init; if (av.color == 'P') { if (atime < 0) { return -atime; }else if(atime < av.blue){ return av.blue-atime; }else{ return av.blue+av.purple-atime; } }else{ if (atime < 0) { return -atime; }else if(atime < av.purple){ return av.purple-atime; }else{ return av.blue+av.purple-atime; } } } int waitTime(int a,int b){ //from a to b vertexType &av = vertex[a]; vertexType &bv = vertex[b]; int atime = getTime(av.dis, a); int btime = getTime(av.dis, b); char acolor = getColor(av.dis,a); char bcolor = getColor(av.dis,b); if (acolor == bcolor) { return 0; } if (abs(atime - btime)) { return min(atime,btime); }else if(acolor == 'P'){ if (abs(av.blue-bv.purple)) { return atime+min(av.blue,bv.purple); }else if(abs(av.purple-bv.blue)){ return atime+av.blue+min(av.purple,bv.blue); }else{ return -1; } }else if(acolor == 'B'){ if (abs(av.purple-bv.blue)) { return atime+min(av.purple,bv.blue); }else if(abs(av.blue-bv.purple)){ return atime+av.purple+min(av.blue,bv.purple); }else{ return -1; } }else{ return -1; } } struct cmp{ bool operator () (int a,int b){ return vertex[a].dis > vertex[b].dis; } }; void dijkstra(){ vertex[str].dis = 0; priority_queue<int,vector<int>,cmp> q; q.push(str); bool vis[305]; memset(vis, 0, sizeof(vis)); while (!q.empty()) { int nown = q.top(); q.pop(); vis[nown] = true; vertexType &nowv = vertex[nown]; for (int i = 0; i < nowv.edge.size(); i++) { int nextn = nowv.edge[i].to; vertexType &nextv = vertex[nextn]; if (vis[nextn]) { continue; } int wait = waitTime(nown,nextn); if (wait == -1) { continue; } if (wait + nowv.dis + nowv.edge[i].cost < nextv.dis) { //relax nextv.dis = wait + nowv.dis + nowv.edge[i].cost; nextv.pre = nown; q.push(nextn); } } } } int main(){ scanf(" %d %d %d %d",&str,&ter,&n,&m); for (int i = 1; i <= n; i++) { scanf(" %c %d %d %d",&vertex[i].color,&vertex[i].init,&vertex[i].blue,&vertex[i].purple); } for (int i = 1; i <= m; i++) { int a = 0,b = 0,c = 0; scanf(" %d %d %d",&a,&b,&c); vertex[a].edge.push_back(edgeType(b,c)); vertex[b].edge.push_back(edgeType(a,c)); } dijkstra(); if (vertex[ter].dis == 0x3f3f3f3f) { printf("0\n"); return 0; } printf("%d\n",vertex[ter].dis); stack<int> path; int curr = ter; while (curr) { path.push(curr); curr = vertex[curr].pre; } while (path.size()>1) { printf("%d ",path.top()); path.pop(); } printf("%d\n",path.top()); path.pop(); return 0; } |
