本文主要是介绍SGU 103. Traffic Lights 带限制最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
每个点有2中颜色 只有一条路上的两个点颜色一样才能通过这条路 最短路加上等待的时间处理 处理的是参考别人的 唉还是太弱了
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int s, e;
int n, m;
int a[333];
int b[333];
int c[333];int first[333], cnt;
struct edge
{int v, w, next;
}G[30000];int d[333];
int p[333];
bool vis[333];
struct HeapNode
{int v, d;HeapNode(){}HeapNode(int v, int d): v(v), d(d){}bool operator < (const HeapNode& rhs) const{return d > rhs.d;}
};void AddEdge(int u, int v, int w)
{G[cnt].v = v;G[cnt].w = w;G[cnt].next = first[u];first[u] = cnt++;G[cnt].v = u;G[cnt].w = w;G[cnt].next = first[v];first[v] = cnt++;}int wait(int t, int x, int y)
{int ans = 0;int t1 = (a[x] + t) % c[x];int t2 = (a[y] + t) % c[y];int tmp;for(int i = 0; i < 4; i++){if((t1 < b[x]) == (t2 < b[y]))return ans;if(t1 < b[x])tmp = b[x] - t1;elsetmp = c[x] - t1;if(t2 < b[y])tmp = min(tmp, b[y] - t2);elsetmp = min(tmp, c[y] - t2);t1 = (t1 + tmp) % c[x];t2 = (t2 + tmp) % c[y];ans += tmp;}return -1;
}void print(int x)
{if(p[x] == -1){printf("%d", x);return;}print(p[x]);printf(" %d", x);
}
void Dijkstra()
{for(int i = 1; i <= n; i++){d[i] = 999999999;p[i] = -1;vis[i] = false;}d[s] = 0;priority_queue <HeapNode> Q;Q.push(HeapNode(s, 0));while(!Q.empty()){HeapNode x = Q.top(); Q.pop();int u = x.v;if(vis[u])continue;vis[u] = 1;for(int i = first[u]; i != -1; i = G[i].next){int v = G[i].v;int x = d[u];int t = wait(x, u, v);if(t != -1 && d[v] > d[u] + G[i].w + t){d[v] = d[u] + G[i].w + t;p[v] = u;Q.push(HeapNode(v, d[v]));}}}if(d[e] != 999999999){printf("%d\n", d[e]);print(e);puts("");}elseputs("0");
}
int main()
{memset(first, -1, sizeof(first));cnt = 0;scanf("%d %d", &s, &e);scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++){char s[10];int r, bl, pu;scanf("%s %d %d %d", s, &r, &bl, &pu);if(s[0] == 'B'){a[i] = bl-r;b[i] = bl;c[i] = bl+pu;}else{a[i] = bl+pu-r;b[i] = bl;c[i] = bl+pu;}}for(int i = 1; i <= m; i++){int u, v, w;scanf("%d %d %d", &u, &v, &w);AddEdge(u, v, w);}Dijkstra();return 0;
}这篇关于SGU 103. Traffic Lights 带限制最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
