首页 > 代码库 > Codeforces_449B 最短路+统计
Codeforces_449B 最短路+统计
也是给这个题目跪了一天。。。时间不多了,也不多讲
首先要用 nlogn的优先队列dijstla来求最短路,n^2的会超时,不过发现SPFA好像也可以过,他的复杂度应该介于NlogN和N^2之间。
然后统计可以去掉的铁路条数才是难点
一开始我采用边跑最短路边标记,最后再统计,发现漏了好多情况,自己想了个数据都过不了,即如果当前的铁道和另外一个铁路都能访问该点,实际应该去掉当前的这个铁路,但我这种方案根本探测不出来这种情况
最好的方法就是边跑最短路边探测了,聪哥就是这样做,然后我还是谨慎了些,采用数组记录,但是我坑在一个地方,就是优先队列的时候,我调用外部的数组值作为比较函数的变量,然后总是过不了第六组数据,最后发现是这个问题。真是坑死人,优先队列的比较函数一定只能调用内部值,千万别调外部的,血泪教训啊
还有个坑的地方就是我用的邻接表是先访问火车路,再访问公路,不像聪哥是先访问公路,后来铁路一上来,直接比较就行了。。。我这样的,有可能铁路边一出来就变成了最短边,但其实还有可能公路能访问到他,距离相等的公路,那么这个铁边就要去掉了,所以在里面孩子就算被vis了,也特判一下是不是铁路边以及距离相等。
有很多废弃边,尤其是连接一个点可能有多条铁路,在读入数据的时候,就处理掉这些,只留下一个边,这些边留下不仅增加复杂度,还可能造成错误,因为不好判断
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#define LL __int64using namespace std;int n,m,k;const int N = 9*100000+80;int u[N],v[N],nt[N],flag[N],ft[N/8];__int64 e[N];__int64 d[N/8];const LL INF =1LL<<62;int vis[N/8];int inq[N/8];int cnt;int isq[N/8];struct node{ int x,val; bool operator < (const node& rhs) const{ return val>rhs.val; }};void add(int a,int b,int c,int f){ u[cnt]=a; v[cnt]=b; e[cnt]=(LL)c; flag[cnt]=f; nt[cnt]=ft[a]; ft[a]=cnt++;}priority_queue<node> q;void dijstla(){ while (!q.empty()) q.pop(); d[1]=0; q.push((node){1,0}); while (!q.empty()) { node tmp=q.top(); q.pop(); int ux=tmp.x; if (vis[ux]) continue; vis[ux]=1; isq[ux]=0; for (int i=ft[ux];i!=-1;i=nt[i]){ int vx=v[i]; if (d[vx]>d[ux]+e[i]){ if (inq[vx]>0 && flag[i]==0 && ((d[ux]+e[i])<=inq[vx])){ inq[vx]=0; } d[vx]=d[ux]+e[i]; //if (isq[vx]) continue; // else { q.push((node){vx,d[vx]}); //isq[vx]=1; // } } else if (d[vx]==d[ux]+e[i]) { if (flag[i]==0){ inq[vx]=0; } } else if (flag[i]==1){ inq[vx]=0; } } }}int main(){ int a,b,c; while (scanf("%d%d%d",&n,&m,&k)!=EOF) { int ans=0; cnt=0; for (int i=0;i<=n;i++){ ft[i]=-1; d[i]=INF; vis[i]=0; inq[i]=-1; isq[i]=0; } for (int i=0;i<m;i++){ scanf("%d%d%d",&a,&b,&c); add(a,b,c,0); add(b,a,c,0); } int tmp=0; for (int i=0;i<k;i++){ scanf("%d%d",&a,&b); if (inq[a]==-1){ inq[a]=b; } else { ans++; if (inq[a]>b) inq[a]=b; } } for (int i=2;i<=n;i++){ if (inq[i]>0){ add(1,i,inq[i],1); } } dijstla(); for (int i=ft[1];i!=-1;i=nt[i]){ int nx=v[i]; if (flag[i]==1){ if (inq[nx]==0){ ans++; } else if (inq[nx]>0) { if (d[nx]<inq[nx]){ ans++; } } } } printf("%d\n",ans); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。