题解【AcWing176】装满的油箱

标签：add   head   code   names   operator   编号   top   debug   单位   

题面

一开始拿到这个问题并不好做，于是考虑拆点。

考虑将一个点拆成 \(c+1\) 个，每个点表示（编号，剩余油量）。

然后 \(\text{Dijkstra}\) 最短路即可。

每次跑 \(\text{Dijkstra}\) 时，先判断能不能再加 \(1\) 单位的油，然后遍历每一条出边，加入优先队列。

注意节点编号从 \(0\) 开始。

#include 
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define itn int
#define gI gi

using namespace std;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c  '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c  a.sy;
    }
} ;

inline void add(int u, int v, int w)
{
    ver[++tot] = v, nxt[tot] = head[u], edge[tot] = w, head[u] = tot;
}

int vis[maxn][maxx];

inline int Dij(int c, int s, int e)
{
    priority_queue  q;
    memset(vis, 0, sizeof(vis));
    memset(dist, 0x3f, sizeof(dist));
    q.push((Node){0, s, 0});
    while (!q.empty())
    {
        Node now = q.top(); q.pop();
        if (now.now == e) return now.sy;
        if (vis[now.now][now.y]) continue;
        vis[now.now][now.y] = 1;
        if (now.y  now.sy + yj[now.now])
            {
                dist[now.now][now.y + 1] = now.sy + yj[now.now];
                q.push((Node){dist[now.now][now.y + 1], now.now, now.y + 1});
            }
        }
        for (int i = head[now.now]; i; i = nxt[i])
        {
            int v = ver[i], w = edge[i];
            if (now.y >= w)
            {
                if (dist[v][now.y - w] > now.sy)
                {
                    dist[v][now.y - w] = now.sy;
                    q.push((Node){now.sy, v, now.y - w});
                }
            }
        }
    }
    return -1;
}

int main()
{
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    n = gi(), m = gi();
    for (int i = 0; i 

题解【AcWing176】装满的油箱

标签：add   head   code   names   operator   编号   top   debug   单位   

原文地址：https://www.cnblogs.com/xsl19/p/12296217.html