icontofig | 发布于 2020-03-08 16:52:08 | 阅读量 800 | DP
发布于 2020-03-08 16:52:08 | DP

 

题目大意

给定起点和终点以及一些中继点的坐标,距离如题目描述中所示,有0-T这些道路,每种道路上每公里排放CO2数量不同,为ci L / km。

你的车最多能跑B(B≤100)公里,每个中继点连接着另外一些中继点,且连通的道路种类有规定。起点和终点到其它中继点的道路全为种类0.

问能不能从起点到达终点,如果不能输出-1,否则输出最少排放的CO2数。

题解

首先不管别的,先把道路建起来,所有中继点的关系已经给出,而起点和终点需要额外建立两个点,并且设定连向所有的点。

本来看起来是像是个最短路,但是因为有规定最大的里程数,所以普通的最短路算法并不能适用。

但是注意到最大里程数B较小,所以我们可以考虑到某个点在跑了x公里的情况下最小的排放CO2的量是多少,然后通过类似于最短路的BFS对这个维护量进行转移。

即,假设dp[i][j]表示跑到节点i,且已经跑了j公里,所排放的最小CO2的量。

剩下的就是通过类似spfa的bfs进行转移,注意判断边界即可。

 代码

#include <bits/stdc++.h>
using namespace std;
int xs,ys,xt,yt;
const int maxn = 1005;
int T,B,n;
const int INF = 1e9+7;
const int maxe = 1e6+5;
int dp[maxn][105];
int c[105];
struct point{
    int x,y;
}p[maxn];
typedef pair<int,int>PI;
vector<PI>g[maxn];
int dis(int a,int b){
    double x = sqrt(double((p[a].x - p[b].x)*(p[a].x - p[b].x) + (p[a].y - p[b].y) * (p[a].y - p[b].y)));
    return (int)ceil(x);
}
struct node{
    int id,dis,cos,pre;
};
struct edge{
    int to,next,dis,cos;
}e[maxe<<1];
int h[maxn];
int cnt = 0;
void add(int u,int v,int d,int c){
    e[cnt].to = v;e[cnt].dis = d;e[cnt].cos = c;
    e[cnt].next = h[u];h[u] = cnt++;
    return;
}
int ans = 0;
void bfs(int s,int t){
    queue<node>q;
    dp[s][0] = 0;
    ans = INF;
    q.push({s,0,0,-1});
    while(!q.empty()){
        node now = q.front();
        q.pop();
        for(int i = h[now.id];i != -1;i = e[i].next){
            int v = e[i].to;
            if(v == now.pre)continue;
            if(now.dis + e[i].dis > B)continue;
            if(v == t){
                ans = min(ans,now.cos + e[i].cos);
                continue;
            }
            if(dp[v][now.dis + e[i].dis] > now.cos + e[i].cos){
                dp[v][now.dis + e[i].dis] = now.cos + e[i].cos;
                q.push({v,now.dis + e[i].dis,now.cos+e[i].cos,now.id});
            }
        }
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> xs >> ys;
    cin >> xt >> yt;
    cin >> B;
    cin >> c[0];
    cin >> T;
    for(int i = 1;i <= T;++i){
        cin >> c[i];
    }
    cin >> n;
    memset(h,-1,sizeof(h));
    for(int i = 0;i < n;++i){
        cin >> p[i].x >> p[i].y;
        int l,a,b;
        cin >> l;
        while(l--){
            cin >> a >> b;
            g[i].push_back(make_pair(a,b));
        }
    }
    for(int i = 0;i < n;++i){
        for(int j = 0;j < g[i].size();++j){
            int di = dis(i,g[i][j].first);
            add(i,g[i][j].first,di,di*c[g[i][j].second]);
            add(g[i][j].first,i,di,di*c[g[i][j].second]);
        }
    }
    p[n] = {xs,ys};
    p[n+1] = {xt,yt};
    for(int i = 0;i < n;++i){
        int di = dis(i,n);
        add(i,n,di,di*c[0]);
        add(n,i,di,di*c[0]);
        di = dis(i,n+1);
        add(i,n+1,di,di*c[0]);
        add(n+1,i,di,di*c[0]);
    }
    int di = dis(n,n+1);
    add(n,n+1,di,di*c[0]);
    add(n+1,n,di,di*c[0]);
    for(int i = 0;i < maxn;++i)
        for(int j = 0;j < 105;++j)
            dp[i][j] = INF;
    dp[n][0] = 0;
    bfs(n,n+1);
    if(ans == INF)ans = -1;
    cout << ans << endl;
    return 0;
}



内容更新于: 2020-03-08 16:52:16
链接地址: http://blog.leanote.com/post/icontofig/SWERC-2019-2020-Problem-G

上一篇: SWERC 2019-20 Problem G. Swapping Places 拓扑排序

下一篇: CodeForces 1303G. Sum of Prefix Sums 点分治+李超线段树

800 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航