D - Silver Cow Party J - Invitation Cards 最短路

佚名 6年前 (2019-05-16) 随笔 1029人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题目思路：

直接进行暴力，就是先求出举行party的地方到每一个地方的最短路，然后再求以每一个点为源点跑的最短路。

还有一种方法会快很多，就是跑两次最短路，一次正向的，另外一次反向的，因为都是只要求每一个位置到源点的最短距离，

所以这样子写就会快很多。

这个想法看完这个题目在脑袋里一闪而过没有仔细想，后来发现可以直接暴力，就忘记了，结果后面有一个数据大的就不行了。。。

#include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <vector> #include <algorithm> #include <map>
#define inf 0x3f3f3f3f
using namespace std; const int maxn = 2e5 + 10; int d[maxn], dis[maxn], n, m; struct node { int from, to, dist; node(int from=0,int to=0,int dist=0):from(from),to(to),dist(dist){} }; struct heapnode { int u, d; heapnode(int u=0,int d=0):u(u),d(d){} bool operator<(const heapnode&a)const { return a.d < d; } }; vector<node>vec[maxn]; bool vis[maxn]; void dij(int s) { priority_queue<heapnode>que; for (int i = 0; i <= n; i++) d[i] = inf; d[s] = 0; memset(vis, 0, sizeof(vis)); que.push(heapnode(s, 0)); while(!que.empty()) { heapnode x = que.top(); que.pop(); int u = x.u; if (vis[u]) continue; vis[u] = 1; for(int i=0;i<vec[u].size();i++) { node e = vec[u][i]; if(d[e.to]>d[u]+e.dist) { d[e.to] = d[u] + e.dist; que.push(heapnode(e.to, d[e.to])); } } } } int main() { int k; scanf("%d%d%d", &n, &m, &k); for(int i=1;i<=m;i++) { int x, y, c; scanf("%d%d%d", &x, &y, &c); vec[x].push_back(node(x, y, c)); } int ans = 0; dij(k); for (int i = 0; i <= n; i++) dis[i] = d[i]; for(int i=1;i<=n;i++) { if (i == k) continue; dij(i); // printf("dis[%d]=%d d[%d]=%d\n", i, dis[i], k, d[k]);
        ans = max(ans, dis[i] + d[k]); } printf("%d\n", ans); return 0; }

http://poj.org/problem?id=1511

这个和上面的题目一个意思

#include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <vector> #include <algorithm> #include <map>
#define inf 0x3f3f3f3f
using namespace std; typedef long long ll; const int maxn = 1e6 + 10; ll d[maxn], dis[maxn]; int n, m; struct node { int from, to; ll dist; node(int from = 0, int to = 0, ll dist = 0) :from(from), to(to), dist(dist) {} }; struct heapnode { int u; ll d; heapnode(int u = 0, ll d = 0) :u(u), d(d) {} bool operator<(const heapnode&a)const { return a.d < d; } }; vector<node>vec[maxn]; bool vis[maxn]; void dij(int s) { priority_queue<heapnode>que; for (int i = 0; i <= n; i++) d[i] = inf; d[s] = 0; memset(vis, 0, sizeof(vis)); que.push(heapnode(s, 0)); while (!que.empty()) { heapnode x = que.top(); que.pop(); int u = x.u; if (vis[u]) continue; vis[u] = 1; for (int i = 0; i < vec[u].size(); i++) { node e = vec[u][i]; if (d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; que.push(heapnode(e.to, d[e.to])); } } } } int a[maxn], b[maxn]; ll c[maxn]; int main() { int t; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) vec[i].clear(); for (int i = 1; i <= m; i++) { scanf("%d%d%lld", &a[i], &b[i], &c[i]); vec[a[i]].push_back(node(a[i],b[i],c[i])); } dij(1); for (int i = 0; i <= n; i++) { dis[i] = d[i]; vec[i].clear(); } for(int i=1;i<=m;i++) { vec[b[i]].push_back(node(b[i], a[i], c[i])); } dij(1); ll ans = 0; for(int i=1;i<=n;i++) { ans += d[i] + dis[i]; } printf("%lld\n", ans); } return 0; }