跳至正文

SGU 103 Traffic Lights 解题报告

算法本质:单源最短路径+简单变形 算  法: 就是单源最短路径,我使用的SPFA,但是和普通单源最短路径不同的是,这个需要把路上所消耗的时间加上等待两边的灯同时亮起的时间这样唯一要耽误点时间实现的就是计算等待的时间。 计算在时间k通过a,b两个路口所需要等待的时间算法如下,如果此时(k)a,b路口的路灯是相同的话那么等待时间为0,如果不同那么就是a路口灯光变色的时间和b路口灯光变色的时间二者的最小时间,但是如果二者相同的话,那么就继续循环,此时k就等于a(或者b)路口灯光变色的时间。 复 杂 度: 时间&空间:O(N^2) de lang="C">#include #include #include #define MAX 300 / 添加这些注释 / #define INF 0x7FFFFFFF struct node{ int color, wait; int wait_1, wait_2; }node[301]; int map[301][300]; int link[301][300]; int count[301]; int queue[300]; int used[301], from[301]; int head, rear; int dist[301]; int min(int a, int b) { return a c + map[a][i]){ dist[b] = c + map[a][i]; from[b] = a; enqueue(b); } } } if(dist[end] == INF){ printf("0\n"); return 0; } printf("%d\n", dist[end]); output(start, end); printf("\n"); return 0; } de>

发表回复

您的电子邮箱地址不会被公开。