S - Layout ——最短路_spfa()算法+前向星+负环+差分约束 快来打我* 2022-06-12 10:53 135阅读 0赞 Think: 1知识点:最短路\_spfa()算法+前向星+负环+差分约束 2题意分析:ml关系的奶牛距离小于等于w,md关系的奶牛距离大于等于w,询问满足条件的情况下1与n之间的最大距离,模型抽象发现不等式组 [vjudge题目链接][vjudge] [可参考博客][Link 1] 以下为Accepted代码 #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int inf = 0x3f3f3f3f; const int N = 1e3 + 4; const int M = 2e4 + 4; struct Edge{ int v; int w; int next; }edge[M]; bool flag; int n, ml, md, cnt, head[N], dis[N], vis[N], num[N]; void add_edge(int u, int v, int w); void spfa(int x); int main(){ int i, u, v, w; while(~scanf("%d %d %d", &n, &ml, &md)){ flag = true, cnt = 0; memset(head, -1, sizeof(head)); for(i = 1; i <= ml; i++){ scanf("%d %d %d", &u, &v, &w); if(u > v) swap(u, v); add_edge(u, v, w);/*差分约束*/ } for(i = 1; i <= md; i++){ scanf("%d %d %d", &u, &v, &w); if(u < v) swap(u, v); add_edge(u, v, -w);/*差分约束*/ } spfa(1); if(!flag) printf("-1\n"); else printf("%d\n", dis[n] == inf? -2: dis[n]); } return 0; } void add_edge(int u, int v, int w){ edge[cnt].v = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; } void spfa(int x){ queue <int> q; while(!q.empty()){ q.pop(); } memset(dis, inf, sizeof(dis)); memset(vis, 0, sizeof(vis)); memset(num, 0, sizeof(num)); dis[x] = 0, vis[x] = 1; q.push(x); num[x]++; while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = 0; for(int i = head[u]; ~i; i = edge[i].next){ int v = edge[i].v; int w = edge[i].w; if(dis[u] + w < dis[v]){ dis[v] = dis[u] + w; if(!vis[v]){ vis[v] = 1; q.push(v); num[v]++; } if(num[v] > n){ flag = false; return; } } } } } [vjudge]: https://vjudge.net/contest/163006#problem/S [Link 1]: http://www.cnblogs.com/kuangbin/archive/2012/08/17/2644643.html
还没有评论,来说两句吧...