GYM102501A Travel

题目链接:https://codeforces.com/gym/102501/problem/A

Solution

观察 w \leq 100,遂知本题是分层图最短路模板。

注意细节

分层图以前写过:点击跳转

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int xs,ys,xd,yd,B,C_0,T,C[N],n,x_[N],y_[N];
vector<pair<int,int> > vec[N];
vector<pair<int,pair<int,int> > > v[N];
int dis[101][N],cov[101][N];
int dist(int x_0,int y_0,int x_1,int y_1){
    return ceil(sqrt((x_0-x_1)*(x_0-x_1)+(y_1-y_0)*(y_1-y_0)));
}
void init(){
    scanf("%d %d",&xs,&ys);
    scanf("%d %d",&xd,&yd);
    scanf("%d",&B);
    scanf("%d",&C_0);
    scanf("%d",&T);
    for(int i=1;i<=T;++i) scanf("%d",&C[i]);
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int l;
        scanf("%d%d%d",&x_[i],&y_[i],&l);
        for(int p=0;p<l;++p){
            int j,m_j;
            scanf("%d%d",&j,&m_j);j++;
            vec[i].push_back(make_pair(j,m_j));
        }
    }
    for(int i=1;i<=n;++i){
        int dis = dist(xs,ys,x_[i],y_[i]);
        int w = dis * C_0 ;
        //printf("i:%d j:%d dis:%d\n",0,i,dis);
        v[0].push_back(make_pair(i,make_pair(dis,w)));
    }
    x_[0]=xs,y_[0]=ys;
    for(int i=0;i<=n;++i){
        int dis = dist(x_[i],y_[i],xd,yd);
        int w = dis * C_0 ; 
        //printf("i:%d j:%d dis:%d\n",i,n+1,dis);
        v[i].push_back(make_pair(n+1,make_pair(dis,w)));
    }
    for(int i=1;i<=n;++i){
        for(auto p:vec[i]){
            int j=p.first,m_j=p.second;
            int dis = dist(x_[i],y_[i],x_[j],y_[j]);
            //printf("i:%d j:%d dis:%d\n",i,j,dis);
            int w = dis * C[m_j];
            v[i].push_back(make_pair(j,make_pair(dis,w)));
            v[j].push_back(make_pair(i,make_pair(dis,w)));
        }
    }
}
void solve(){
    priority_queue<pair<int,pair<int,int> > > q;
    memset(dis,0x3f,sizeof(dis));
    dis[0][0]=0;
    q.push(make_pair(0,make_pair(0,0)));
    while(!q.empty()){
        pair<int,pair<int,int> > now = q.top(); q.pop();
        int d = now.first, x = now.second.first, wn = now.second.second;
        d=-d;
        if(cov[wn][x]) continue;
        cov[wn][x]=1;
        for(auto p:v[x]){
            int to = p.first, pri = p.second.second, di = p.second.first;
            if(wn+di>B) continue;
            if(d+pri>dis[di+wn][to]) continue;
            dis[di+wn][to]=d+pri;
            q.push(make_pair(-(d+pri),make_pair(to,wn+di)));
        }
    }
    int ans=0x7f7f7f7f;
    for(int i=0;i<=B;++i)
        ans=min(ans,dis[i][n+1]);
    if(ans==0x3f3f3f3f) ans=-1;
    printf("%d",ans);
}
int main(){
    init();
    solve();
    return 0;
}

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注