西安邀请赛-M（二分+bfs）

题目链接：https://nanti.jisuanke.com/t/39280

题意：n个点(<=1e5)，m条边(n-1<=m<=1e5)，飞船最开始每次能走长度为0的边，可以走0次。每升级一次花费c，一次可以走的长度+d，可以走的次数+e。问最少花费多少能从1走到n。

思路:这道题比赛时读错题，导致没有花很多时间在这道题。其实这题读懂题后还是比较好做的。要求最少花费，显然最小花费属于[1,1e5]，所以容易想到二分搜索答案。然后用bfs得到买m次后经过多少边能从1到n，不能到达则返回0x3f3f3f3f3f3f3f3f。要注意的是数据范围，会炸int，wa了很多发QAQ。其实不太明白这题-1的情况，因为题目说了图是连通的，那么你总可以通过购买足够的次数来升级，总能到达。但出题人没反应，就判断一下如果结果超出查找范围，也就是图不连通的情况，输出-1。

AC代码：

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;

struct node1{
    int v,w,next;
}a[maxn<<1];

struct node2{
    int p;
    LL s;
}tmp;

int head[maxn],vis[maxn];
int n,m,c,d,e,cnt;

void add(int u,int v,int w){
    a[cnt].v=v;
    a[cnt].w=w;
    a[cnt].next=head[u];
    head[u]=cnt++;
}

LL bfs(int num){
    LL len=1LL*d*num;
    queue<node2> q;
    memset(vis,0,sizeof(vis));
    tmp.p=1,tmp.s=0;
    q.push(tmp);
    while(!q.empty()){
        node2 nw=q.front();q.pop();
        int np=nw.p,ns=nw.s;
        if(np==n)
            return 1LL*ns;
        for(int i=head[np];i!=-1;i=a[i].next){
            if(!vis[a[i].v]&&a[i].w<=len){
                vis[a[i].v]=1;
                tmp.p=a[i].v,tmp.s=ns+1;
                q.push(tmp);
            }
        }
    }
    return 0x3f3f3f3f3f3f3f3f;
}

int main(){
    int Max=0;
    scanf("%d%d%d%d%d",&n,&m,&c,&d,&e);
    memset(head,-1,sizeof(head));
    for(int i=0;i<m;++i){
        int t1,t2,t3;
        if(t3>Max) Max=t3;
        scanf("%d%d%d",&t1,&t2,&t3);
        add(t1,t2,t3);
        add(t2,t1,t3);
    }
    int l=1,r=100000,m;
    while(l<=r){
        m=(l+r)>>1;
        if(bfs(m)<=1LL*m*e) r=m-1;
        else l=m+1;
    }
    if(l<=100000)
        printf("%lld
",1LL*c*l);
    else
        printf("-1
");
    return 0;
}