国外有哪些做服装的网站有哪些方面,最近三天发生的重要新闻,网页打不开但是有网什么原因无法显示此网页,手机和wap网站建设LOJ3156 题面就不放了 , 放一下数据范围 . 看到 \(n2000,m4000\) 就想到直接 \(dfs\) 到底 , 居然就过了前 \(4\)个 样例 , 最后一个要 \(2s\) . 后来写了 \(AB0\) 的 \(5\) 分 , 我知道写的是错的 , 还是交了以下这份代码 . ( LOJ 数据应该是官方数据 ) 得分 \(70\) .…LOJ3156 题面就不放了 , 放一下数据范围 . 看到 \(n2000,m4000\) 就想到直接 \(dfs\) 到底 , 居然就过了前 \(4\)个 样例 , 最后一个要 \(2s\) . 后来写了 \(AB0\) 的 \(5\) 分 , 我知道写的是错的 , 还是交了以下这份代码 . ( LOJ 数据应该是官方数据 ) 得分 \(70\) . 晚上到 LOJ 上一测 , 发现如果直接跑我的暴力有 \(80\) 分 , 又到 \(AC\) 记录里面随便看了一篇比较优秀的 , 改在后面 . #includecstdio
#includeiostream
#includecstring
#includealgorithm
#includecassert
#includequeue
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout#xxendl
using namespace std;
typedef long long LL;
const int INF1e97;
inline LL read(){register LL x0,f1;register char cgetchar();while(c48||c57){if(c-)f-1;cgetchar();}while(c48c57)x(x3)(x1)(c15),cgetchar();return f*x;
}const int N100005;
const int M200005;struct Edge{int v,s,t,nxt;
}e[M];
int first[N],Ecnt0;
inline void Add_edge(int u,int v,int s,int t){e[Ecnt](Edge){v,s,t,first[u]};first[u]Ecnt;
}int n, m, A, B, C;inline LL calc(int x){return 1ll * A * x * x 1ll * B * x C;
}namespace baoli{LL ans INF;inline void dfs(int u, int time, LL cost){if(u n){ans min(ans, cost time);}for(int i first[u]; i; i e[i].nxt){int v e[i].v, s e[i].s, t e[i].t;if(s time) continue;dfs(v, t, cost calc(s - time));}}inline void main(){dfs(1, 0, 0);printf(%lld\n, ans);exit(0);}
};namespace Subtask1{ // A 0 B 0int dis[N], time[N];queue int q;LL ans INF;inline void Return(LL ans){printf(%lld\n, ans);exit(0);}inline void main(){q.push(1);memset(dis, 0x3f, sizeof dis);dis[1] 0;while(!q.empty()){int u q.front(); q.pop();for(int i first[u]; i; i e[i].nxt){int v e[i].v;if(time[u] e[i].s) continue;if(dis[u] 1 dis[v]){dis[v] dis[u] 1;time[v] e[i].t;q.push(v);}if(v n) ans min(ans, 1ll * (dis[u] 1 1) * C e[i].t);}}Return(ans);assert(false);}/*inline void main(){q.push((Node){1, 0, 0});while(!q.empty()){int u q.front().x, d q.front().dis, t q.front().time; q.pop();for(int i first[u]; i; i e[i].nxt){int v e[i].v;if(e[i].t t) continue;if(}}}*/
};int main(){
#ifndef filefreopen(route.in,r,stdin);freopen(route.out,w,stdout);
#endifn read(), m read(), A read(), B read(), C read();for(register int i 1; i m; i){register int x read(), y read(), p read(), q read();Add_edge(x, y, p, q);}if(n 2000 m 4000) baoli::main();if(A 0 B 0) Subtask1::main();
}LOJ上的一份AC代码 我没注意到时间 \(q1000\) , 这样的话 \(O(nq)O(1e8)\) 应该可以卡过? 直接 \(dp\) 有人得了 95分 . 把列车 按照时间排序 , 再依次更新 , 这样 \(1e8\) 就跑不满 , 直接就过了 . 可以用 \(vector\) 存状态 . 对于这个数据范围就当 \(O(nq)\) 是正解好了 . #includecstdio
#includecstring
#includeiostream
#includealgorithm
#includevector
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout#xxendl
using namespace std;
typedef long long LL;
const LL INF1e187;
inline LL read(){register LL x0,f1;register char cgetchar();while(c48||c57){if(c-)f-1;cgetchar();}while(c48c57)x(x3)(x1)(c15),cgetchar();return f*x;
}const int N 1e5 5;
const int M 2e5 5;struct Node{int x, y, p, q;
}a[M];
inline bool cmp1(Node a, Node b){if(a.p b.p) return a.q b.q;return a.p b.p;
}vector LL f[N];
vector int t[N];
int n, m, A, B, C;inline LL calc(int x){return 1ll * A * x * x 1ll * B * x C;
}int main(){
#ifndef filefreopen(route.in,r,stdin);freopen(route.out,w,stdout);
#endifn read(), m read(), A read(), B read(), C read();for(int i 1; i m; i){a[i].x read(), a[i].y read(), a[i].p read(), a[i].q read();}sort(a 1, a m 1, cmp1);f[1].push_back(0), t[1].push_back(0);for(int i 1; i m; i){int x a[i].x, y a[i].y, p a[i].p, q a[i].q;int tt -1;for(int j 0; j t[y].size(); j)if(t[y][j] q) {tt j; break;}for(int j 0; j f[x].size(); j){if(t[x][j] p) continue;int len p - t[x][j];if(tt -1){f[y].push_back(f[x][j] calc(len));t[y].push_back(q);tt f[y].size() - 1;}else if(f[x][j] calc(len) f[y][tt]){f[y][tt] f[x][j] calc(len);}}}LL ans INF;for(int i 0; i f[n].size(); i)ans min(ans, f[n][i] t[n][i]);printf(%lld\n, ans);
}转载于:https://www.cnblogs.com/lizehon/p/11197337.html
