昨天訓練賽感覺跟吃了翔一樣。做了兩題都沒做出來。 題意： 整個城市有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;}新聞熱點
疑難解答
