AtCoder Beginner Contest 143 E.Travel by Car(最短路)

题目链接

大意:给你一个无向带权图,给你一些询问点, s , t s,t s,t,你从s出发有 l l l升的油,走 x x x距离耗费 x x x油,你可以在点上加油,不能在路径上加油,问你到 t t t最少加几次油。

显然的最短路问题,预处理出所有起点到其他地方的最少加油次数即可。
注意优化复杂度。。。。。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=3e2+10;
#define fi first
#define se second
#define pb push_back
LL dis[N][N];
int n,m,l,vis[N];
struct uzi{
    int a;
    LL b;
    LL c;
    bool operator <(const uzi & t)const{
        if(c==t.c)return b<t.b;
        return c>t.c;
    }
};
vector<pair<int,int> >v[N];

LL tmp[N][N];
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m>>l;
    for(int i=1;i<=m;i++){
        int s,t,w;
        cin>>s>>t>>w;
        v[s].pb({t,w});
        v[t].pb({s,w});
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j)dis[i][j]=LLONG_MAX,tmp[i][j]=0;
            else dis[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        priority_queue<uzi>q;
        memset(vis,0,sizeof vis);
        q.push({i,l,0});
        tmp[i][i]=l;
        while(!q.empty()){
            auto now=q.top();
            q.pop();
            vis[now.a]=0;
            for(auto k:v[now.a]){
                int cost=k.se;
                int tmpa=tmp[i][now.a];
                if(tmpa>=cost){
                    if(dis[i][k.fi]<dis[i][now.a])continue;
                    if(dis[i][k.fi]==dis[i][now.a]){
                        if(tmp[i][k.fi]>=tmpa-cost)continue;
                    }
                    dis[i][k.fi]=dis[i][now.a];
                    tmp[i][k.fi]=tmpa-cost;
                    if(!vis[k.fi])q.push({k.fi,tmpa-cost,dis[i][now.a]}),vis[k.fi]=1;
                }else if(l>=cost){
                    int need=1;
                    cost=need*l-cost;
                    if(dis[i][k.fi]<dis[i][now.a]+need)continue;
                    if(dis[i][k.fi]==dis[i][now.a]+need){
                        if(tmp[i][k.fi]>=cost)continue;
                    }
                    tmp[i][k.fi]=cost;
                    dis[i][k.fi]=dis[i][now.a]+need;
                    if(!vis[k.fi])q.push({k.fi,cost,need+dis[i][now.a] }),vis[k.fi]=1;
                }else {
                    continue;
                }
            }
        }
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
        int s,t;
        cin>>s>>t;
        if(dis[s][t]==LLONG_MAX)cout<<-1<<endl;
        else cout<<dis[s][t]<<endl;
    }
    return 0;
}

全部评论

相关推荐

11-09 14:54
已编辑
华南农业大学 产品经理
大拿老师:这个简历,连手机号码和照片都没打码,那为什么关键要素求职职位就不写呢? 从上往下看,都没看出自己到底是产品经理的简历,还是电子硬件的简历? 这是一个大问题,当然,更大的问题是实习经历的描述是不对的 不要只是去写实习流程,陈平,怎么去开会?怎么去讨论? 面试问的是你的产品功能点,是怎么设计的?也就是要写项目的亮点,有什么功能?这个功能有什么难处?怎么去解决的? 实习流程大家都一样,没什么优势,也没有提问点,没有提问,你就不得分 另外,你要明确你投的是什么职位,如果投的是产品职位,你的项目经历写的全都是跟产品无关的,那你的简历就没用 你的面试官必然是一个资深的产品经理,他不会去问那些计算机类的编程项目 所以这种四不像的简历,在校招是大忌
点赞 评论 收藏
分享
一颗宏心:华为HR晚上过了十二点后还给我法消息。
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务