首页 > 代码库 > Codeforces Round #257(Div.2) D Jzzhu and Cities --SPFA
Codeforces Round #257(Div.2) D Jzzhu and Cities --SPFA
题意:n个城市,中间有m条道路(双向),再给出k条铁路,铁路直接从点1到点v,现在要拆掉一些铁路,在保证不影响每个点的最短距离(距离1)不变的情况下,问最多能删除多少条铁路
分析:先求一次最短路,铁路的权值大于该点最短距离的显然可以删去,否则将该条边加入图中,再求最短路,记录每个点的前一个点,然后又枚举铁路,已经删去的就不用处理了,如果铁路权值大于该点最短距离又可以删去,权值相等时,该点的前一个点如果不为1,则这个点可以由其他路到达,这条铁路又可以删去。
由于本题中边比较多,最多可以有8x10^5条,所以用邻接链表会超时,最好用vector来存储边。
Time:296 ms Memory:30968 KB
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>#include <vector>#include <queue>#define lll __int64using namespace std;#define N 100006struct Edge{ int v; lll w; Edge(int _v,lll _w) { v = _v; w = _w; } Edge(){}};struct Train{ int v; lll w;}T[N];vector<Edge> G[N];lll dis[N];int n,m;int head[N],tot,pre[N];int cut[N],vis[N];queue<int> que;void SPFA(int s){ while(!que.empty()) que.pop(); memset(vis,0,sizeof(vis)); vis[s] = 1; que.push(s); for(int i=0;i<=n;i++) dis[i] = 1000000000000000LL; dis[s] = 0; while(!que.empty()) { int u = que.front(); que.pop(); vis[u] = 0; for(int i=0;i<G[u].size();i++) { int v = G[u][i].v; lll w = G[u][i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if(!vis[v]) { vis[v] = 1; que.push(v); } } } }}void SPFA2(){ while(!que.empty()) { int u = que.front(); que.pop(); vis[u] = 0; for(int i=0;i<G[u].size();i++) { int v = G[u][i].v; lll w = G[u][i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; pre[v] = u; if(!vis[v]) { que.push(v); vis[v] = 1; } } else if(dis[v] == dis[u] + w && pre[v] < u) pre[v] = u; } }}int main(){ int i,j,k; int u,v,y; lll w; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { tot = 0; for(i=0;i<=n;i++) G[i].clear(); memset(head,-1,sizeof(head)); memset(cut,0,sizeof(cut)); memset(pre,-1,sizeof(pre)); for(i=0;i<m;i++) { scanf("%d%d%I64d",&u,&v,&w); G[u].push_back(Edge(v,w)); G[v].push_back(Edge(u,w)); } for(i=0;i<k;i++) { scanf("%d%I64d",&y,&w); T[i].v = y; T[i].w = w; } SPFA(1); int cnt = 0; for(i=0;i<k;i++) { int v = T[i].v; lll w = T[i].w; if(dis[v] <= w) { cut[i] = 1; cnt++; } else { G[1].push_back(Edge(v,w)); G[v].push_back(Edge(1,w)); pre[v] = 1; dis[v] = w; que.push(v); vis[v] = 1; } } SPFA2(); for(i=0;i<k;i++) { if(cut[i]) continue; int v = T[i].v; lll w = T[i].w; if((dis[v] == w && pre[v] != 1) || dis[v] < w) cnt++; } printf("%d\n",cnt); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。