POJ3662

大意：n个点p条边的无向图，求在删去k条边后使1和n号点联通路径上的最长边最小值。

一开始理解错题意以为是分层图求最短路径，结果写完发现k太大了发现事情没有那么简单（讨厌英语题面！）

说一下解法吧，二分答案，尽量小，每次二分完跑最短路径，但是要重置边权。即把比答案小的边改为0，比答案大的改为1，若最短路径比k大，就加答案；反之亦然。

（还好都有最短路径算没白写）

唯一的一点技巧：最初想着每次找完mid把所有边的权值改一下，觉得太麻烦了，那么就每次dijkstra加点的时候判断一下吧！（反正又占不了多少时间……吧）

#include<iostream>

#include<vector>

#include<cstdio>

#include<queue>

#include<cctype>

#include<algorithm>

#include<cstring>

using namespace std;

inline int read()

{

    int x=0,w=0;char c=getchar();

    while(!isdigit(c))w|=c=='-',c=getchar();

    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();

    return w?-x:x;

}

namespace star

{

    const int maxn=1010,maxm=1000010;

    int n,m,k;

    int ecnt,head[maxn],nxt[maxm],t[maxm],val[maxm];

    inline void addedge(int from,int to,int dis){

        t[++ecnt]=to;nxt[ecnt]=head[from];head[from]=ecnt;val[ecnt]=dis;

    }

    typedef pair<int,int> pii;

    int dis[maxn];

    inline void dijkstra(int mid)

    {

        priority_queue<pii,vector<pii >,greater<pii  > > q;

        q.push(make_pair(0,1));

        memset(dis,0x3f3f3f3f,sizeof dis);

        dis[1]=0;

        while(!q.empty())

        {

            int x=q.top().second;q.pop();

            for(int i=head[x];i;i=nxt[i]){

                int u=t[i];

                if(dis[u]>dis[x]+(val[i]>mid)){

                    dis[u]=dis[x]+(val[i]>mid);

                    q.push(make_pair(dis[u],u));

                }

            }

        }

    }

    inline void work()

    {

        n=read(),m=read(),k=read();

        int mlen=0;

        for(int a,b,c,i=1;i<=m;i++)

        {

            a=read(),b=read(),c=read();

            mlen=max(mlen,c);

            addedge(a,b,c);

            addedge(b,a,c);

        }

        int l=0,r=mlen;

        while(l<r){

            int mid=l+r>>1;

            dijkstra(mid);

            if(dis[n]==0x3f3f3f3f){

                printf("-1\n");return;

            }

            if(dis[n]>k)l=mid+1;

            else r=mid;

        }

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

    }

}

int main()

{

    star::work();

    return 0;

}

/*

5 7 1

1 2 5

3 1 4

2 4 8

3 2 3

5 2 9

3 4 7

4 5 6

*/

巴特西

POJ3662

最新文章

热门文章