codeforces Jzzhu and Cities

2019-11-06 06:39:12

字体：大中小

来源：转载

供稿：网友

昨天训练赛感觉跟吃了翔一样。做了两题都没做出来。题意：整个城市有m条公路，和k条铁路，让你求可以删除多少条铁路，但是所有城市的最短距离不能变。一开始的想法就是如果最短路里面包含有铁路，那么就是不可以删除，但是不会实现，后来看到有一个队通过先最短路公路再最短路铁路，居然卡过了！！！！！！！！！害我也学他们弄了好久还是卡不过，今天看了看别人的题解，看到了一开始想法的实现，比较麻烦，入队的不仅是nd，还有当前点的状态（也就是有没有铁路在里面）也入队了，用pair 既可！！！！无语了。两种方法，都差不多，第二种就是让弄个数组 bus 先让铁路达到的点为 1，如果最后收缩这些点的是铁路，那么bus为0，如果最后收缩这些点的是公交那么bus为1. 最后统计一下，这些铁路的点最后是被谁给收缩的。

#include <cstdio>#include <algorithm>#include <queue>#include <cstring>#include <iostream>using namespace std;typedef long long LL;#define N 1000005#define M 2000005vector<int> res;const LL inf = 1e17;struct node{ int v, nxt; LL w; int flag;}edge[M];struct nd{ int p; LL d; nd(){} nd(LL _d, int _to):d(_d), p(_to) {} bool Operator < (const nd &a) const { return d > a.d; }};int tot, n, m, nn, used[N], head[N];LL da[N];int ff[N];void add(int u, int v, LL w,int ff){ edge[tot].v = v; edge[tot].w = w; edge[tot].flag=ff; edge[tot].nxt = head[u]; head[u] = tot++;}int cc=0;struct cmp{ bool operator()(const pair<int, nd> &x, const pair<int, nd> &y) { if(x.second.d!=y.second.d)return x.second.d > y.second.d; return x.first > y.first; }};typedef pair<int,nd> pp;void Dijkstra(int s, LL d[]){ PRiority_queue<pp,vector<pp>,cmp> que; while(!que.empty()) que.pop(); memset(used, 0, sizeof(used)); d[s] = 0; que.push(pp(0,nd(d[s], s))); while(!que.empty()) { pp top = que.top(); que.pop(); int u = top.second.p; if(used[u]) continue; used[u] = 1; if(top.first==1) cc++; for(int k = head[u]; ~k; k = edge[k].nxt) { int v = edge[k].v; if(used[v]) continue; int w = edge[k].w; int train = edge[k].flag; if(d[u]+w <=d[v]) { d[v] = d[u] + w; que.push(pp(train,nd(d[v], v))); } } }}LL db[N];LL len[N];int main(){ int k; scanf("%d %d %d",&nn,&m,&k); memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++) { int a,b; LL c; scanf("%d%d%lld",&a,&b,&c); add(a,b,c,0); add(b,a,c,0); } for(int i = 0 ; i <= nn; i++) da[i] = inf; for(int i=1;i<=k;i++) { int a; LL c; scanf("%d%lld",&a,&c); add(1,a,c,1); add(a,1,c,1); } Dijkstra(1,da); // for(int i=1;i<=nn;i++) // { // cout<<da[i]<<" "; // } // cout<<endl; cout<<k-cc<<endl;}

第二种方法

#include <cstdio>#include <algorithm>#include <queue>#include <cstring>#include <iostream>using namespace std;typedef long long LL;#define N 1000005#define M 2000005vector<int> res;const LL inf = 1e17;struct node{ int v, nxt; LL w; int flag;}edge[M];struct nd{ int p; LL d; nd(){} nd(LL _d, int _to):d(_d), p(_to) {} bool operator < (const nd &a) const { return d > a.d; }};int tot, n, m, nn, used[N], head[N];LL da[N];int ff[N];void add(int u, int v, LL w,int ff){ edge[tot].v = v; edge[tot].w = w; edge[tot].flag=ff; edge[tot].nxt = head[u]; head[u] = tot++;}int cc=0;int bus[N],train[N],len[N];void Dijkstra(int s, LL d[]){ priority_queue<nd> que; while(!que.empty()) que.pop(); memset(used, 0, sizeof(used)); d[s] = 0; que.push(nd(d[s], s)); while(!que.empty()) { nd top = que.top(); que.pop(); int u = top.p; if(used[u]) continue; used[u] = 1; for(int k = head[u]; ~k; k = edge[k].nxt) { int v = edge[k].v; int w = edge[k].w; int kind=edge[k].flag; if(d[u]+w <d[v]) { bus[v]=0; if(kind==0) bus[v]=1; d[v] = d[u] + w; que.push(nd(d[v], v)); } else if(d[u]+w==d[v]) if(kind==0) bus[v]=1; } }}int main(){ int k; scanf("%d %d %d",&nn,&m,&k); memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++) { int a,b; LL c; scanf("%d%d%lld",&a,&b,&c); add(a,b,c,0); add(b,a,c,0); } for(int i = 0 ; i <= nn; i++) { da[i] = inf; bus[i]=0; } for(int i=1;i<=k;i++) { int a; LL c; scanf("%d%lld",&a,&c); add(1,a,c,1); train[i]=a; len[i]=c; } Dijkstra(1,da); for(int i=1;i<=k;i++) { int v=train[i]; if(da[v]<len[i]) ++cc; else{ if(bus[v]==0) bus[v]=1; else cc++; } } cout<<cc<<endl;}

上一篇：webx3学习之旅——webx项目导入eclipse并部署tomcat

下一篇：装配Bean