首页 > 代码库 > Codeforces_449B 最短路+统计

Codeforces_449B 最短路+统计

2024-07-13 13:16:29   220人阅读

也是给这个题目跪了一天。。。时间不多了，也不多讲

首先要用 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;}

　　


联系
我们