ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2015) G. It is all about wisdom (二分,单源最短路)

题意:有\(n\)个点,\(m\)条边,只有当你的智力值大于这条边的\(w\)才能走,问在花费不超过\(k\)的情况下,从\(1\)走到\(n\)的所需的最小智力值.
题解:这题比赛为什么没想出来呢?赛后看题解发现可以二分答案然后跑最短路来check,网上的题解全都是SPFA啊,我还是喜欢写dijkstra qwq.

代码:

struct misaka{

    int out;

    int val;

    int wis;

}e;

int t;

int n,m,k;

vector<misaka> v[N];

int dis[N];

bool st[N];

bool dijkstra(int x){

    me(dis,INF,sizeof(dis));

    me(st,false,sizeof(st));

    priority_queue<PII,vector<PII>,greater<PII>> h;

    h.push({0,1});

    while(!h.empty()){

        auto tmp=h.top();

        h.pop();

        int node=tmp.se;

        int dist=tmp.fi;

        if(st[node]) continue;

        st[node]=true;

        for(auto w:v[node]){

            int j=w.out;

            if(x<w.wis || dist+w.val>k) continue;

            if(dis[j]>dist+w.val){

                dis[j]=dist+w.val;

                h.push({dis[j],j});

            }

        }

    }

    if(dis[n]<k) return true;

    return false;

}

int main() {

    //ios::sync_with_stdio(false);cin.tie(0);

    scanf("%d",&t);

    while(t--){

        scanf("%d %d %d",&n,&m,&k);

        for(int i=1;i<=m;++i){

            int a,b,c,w;

            scanf("%d %d %d %d",&a,&b,&c,&w);

            v[a].pb({b,c,w});

            v[b].pb({a,c,w});

        }

        int l=1,r=1e9;

        bool flag=false;

        while(l<r){

            int mid=(l+r)>>1;

            if(dijkstra(mid)){

                flag=true;

                r=mid;

            }

            else{

                l=mid+1;

            }

        }

        if(flag) printf("%d\n",l);

        else puts("-1");

        for(int i=1;i<=n;++i){

            v[i].clear();

        }

    }

    return 0;

}

巴特西

ACM International Collegiate Programming Contest, Egyptian Collegiate Programming Contest (ECPC 2015) G. It is all about wisdom (二分,单源最短路)

最新文章

热门文章