Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
dfs的spfa判环In Reply To:只能优化到32ms?怎么优化到0ms呢...,顺便贴代码 Posted by:xuesu at 2014-07-20 22:31:45 #include <stdio.h> #include <string.h> int n, m, s, u[20005], v[20005], first[105], next[20005], cnt; int sum[101], vis[101], rear, front; double r[20005], c[20005], d[101], vv; struct node{ int key; double mon; }queue[3005]; void addedge(int st, int ed, double R, double C) { u[++cnt] = st; v[cnt] = ed; r[cnt] = R; c[cnt] = C; next[cnt] = first[st]; first[st] = cnt; } int spfa(int s, double k) { int end; double money; vis[s] = 1; for (int i = first[s]; i; i = next[i]) { end = v[i]; if ((d[s] - c[i]) * r[i] > d[end]) { d[end] = (d[s] - c[i]) * r[i]; if (!vis[end]) { if (spfa(end, d[end])) return 1; } else return 1; } } vis[s] = 0; return 0; } int main() { freopen("1.in", "r", stdin); scanf("%d%d%d%lf", &n, &m, &s, &vv); int x, y; double Rab, Cab, Rba, Cba; for (int i = 1; i <= m; i++) { scanf("%d%d%lf%lf%lf%lf", &x, &y, &Rab, &Cab, &Rba, &Cba); addedge(x, y, Rab, Cab); addedge(y, x, Rba, Cba); } memset(d, 0, sizeof(d)); memset(vis, 0, sizeof(vis)); d[s] = vv; if (spfa(s, vv)) printf("YES\n"); else printf("NO\n"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator