Wannafly 练习赛7 D 珂朵莉的无向图

题目链接https://www.nowcoder.com/acm/contest/38/D

题意:略。

思路:居然每次暴力跑BFS就可以过了...果然我还是不会算复杂度...这里我直接用dijkstra,距离大于s的时候就不再进行下去。

#include <bits/stdc++.h>
using namespace std;
const int maxn=5000+5;
struct Edge{
    int from,to,dis;
};
struct HeapNode{
    int d,u;
    bool operator<(const HeapNode& rhs)const{
        return d>rhs.d;
    }
};
struct Dijkstra{
    int n,m;
    vector<Edge>edges;
    vector<int>G[maxn];
    bool done[maxn];
    int d[maxn];

    void init(int n){
        this->n=n;
        for (int i=0;i<=n;i++) G[i].clear();
        edges.clear();
    }

    void AddEdge(int from,int to,int dist){
        edges.push_back(Edge{from,to,dist});
        m=edges.size();
        G[from].push_back(m-1);
    }

    void dijkstra(int t,int s){
        priority_queue<HeapNode>Q;
        for (int i=1;i<=n;i++) d[i]=1000000000;
        for (int i=1;i<=t;i++){
            int x;scanf("%d",&x);
            d[x]=0;
            Q.push(HeapNode{0,x});
        }
        memset(done,false,sizeof(done));
        int ans=0;
        while (!Q.empty()){
            HeapNode cur=Q.top();Q.pop();
            if (done[cur.u]) continue;
            done[cur.u]=true;
            if (d[cur.u]<=s) ans++;
            else continue;
            for (int i=0;i<(int)G[cur.u].size();i++){
                Edge &e=edges[G[cur.u][i]];
                int v=e.to;
                if (d[v]>d[cur.u]+e.dis){
                    d[v]=d[cur.u]+e.dis;
                    Q.push(HeapNode{d[v],v});
                }
            }
        }
        printf("%d\n",ans);
    }
}solver;
int n,m,q;
int main(){
    scanf("%d%d%d",&n,&m,&q);
    solver.init(n);
    for (int i=1;i<=m;i++){
        int u,v;scanf("%d%d",&u,&v);
        solver.AddEdge(u,v,1);
        solver.AddEdge(v,u,1);
    }
    for (;q--;){
        int t,s;scanf("%d%d",&t,&s);
        solver.dijkstra(t,s);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注