poj 3662 二分最短路（建模与转化）

二分给出的p条边，把大于的都当做电信赠送的线路，小于等于的都当做农夫自己买的线路。

前者权值设为1，后者权值设为0，则最短路跑出来的结果和k值比较就知道是否满足，继续二分。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<vector>
#include<algorithm>
#include<set>
#include<stack>
#include<iterator>
#include<queue>
#include<ctime>
#include<bitset>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll long long
#define lson l,m,(rt<<1)
using namespace std;
#include<iostream>
#include<math.h>
#include<fstream>
using namespace std;
int n;
int v[1024],path[1024];
int map[1024][1024],dis[1024];
int p,k;
int Dijkstra(int s)
{
     int i,j;
     for(i=1;i<=n;i++)
     {
        v[i]=0;
        dis[i]=map[s][i];
     }
     dis[s]=0;
     for(i=1;i<=n;i++)
     {
        int min=10000000;
        int pos=0;
        for(j=1;j<=n;j++)
        {
            if(!v[j] )
                if(dis[j]<min)
                {
                    pos=j;
                    min=dis[j];
                }
        }
        v[pos]=1;
        for(j=1;j<=n;j++)
        {
            int p;
            if(!v[j])
                if(p=map[pos][j]+dis[pos],p<dis[j])
                {
                    dis[j]=p;
                }
        }
    }
    return dis[n];
}
struct node
{
    int x,y;
    int d;
}ve[200000];
void build(int lim)
{
    memset(map,0x3f,sizeof(map));
    for(int i=1;i<=p;i++)
    {
        if(ve[i].d<=lim)
        {
            map[ve[i].x][ve[i].y]=map[ve[i].y][ve[i].x]=0;
     //       cout<<v[i].x<<" "<<v[i].y<<endl;
        }
        else map[ve[i].x][ve[i].y]=map[ve[i].y][ve[i].x]=1;
    }
}
bool cmp(node a,node b)
{
    return a.d<b.d;
}
int main()
{
    int a,b,c;
    while(scanf("%d%d%d",&n,&p,&k)!=EOF)
    {
        for(int i=1;i<=p;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            ve[i].x=a;ve[i].y=b;ve[i].d=c;
        }
        sort(ve+1,ve+1+p,cmp);
        build(0);
        int val=Dijkstra(1);
        if(val<=k)
        {
            printf("0\n");
            continue;
        }
        else if(val>1000000)
        {
            printf("-1\n");
            continue;
        }
        int l=1,r=p,mid;
        int ans;
        while(l<=r)
        {
            mid=(l+r)>>1;
            build(ve[mid].d);
            if(Dijkstra(1)<=k) {ans=mid;r=mid-1;}
            else l=mid+1;
        }
        printf("%d\n",ve[ans].d);
    }
    return 0;
}

poj 3662 二分最短路（建模与转化）

原文：http://blog.csdn.net/t1019256391/article/details/19622611