andyli

题解 UVA10537 【The Toll! Revisited】
尽管和普通的最短路不尽相同,本题仍然可以用$Dijkstra$算法的思路解决,所不同的是需进行逆推而非顺推。令$d...
扫描右侧二维码阅读全文
03
2019/07

题解 UVA10537 【The Toll! Revisited】

尽管和普通的最短路不尽相同,本题仍然可以用$Dijkstra$算法的思路解决,所不同的是需进行逆推而非顺推。令$d[i]$表示进入结点$i$之后,至少要有$d[i]$单位的货物,到达目的地时货物数量才足够,则每次选择一个$d[i]$最小的未标号结点,更新它的所有前驱结点的$d$值即可算出所有的$d$值,然后在输出路径时根据$d$值可以直接构造字典序最小解。需要注意的是,$d[i]$可能会超过无符号$32$位整数的范围,需要用$long long$。
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 60;
using LL = long long;
const LL INF = -1ull / 2;
bool vis[maxn], G[maxn][maxn];  // 标记
LL d[maxn];  // d[i]表示从点i出发(已经交过点i的税了)时至少要带多少东西,到dest时还能剩p个东西

int Read()
{
    char s[9];
    scanf("%s", s);
    return isupper(s[0]) ? (s[0] - 'A') : (s[0] - 'a' + 26);
}
char alpha(int u) { return u < 26 ? 'A' + u : 'a' + (u - 26); }
// 拿着item个东西去结点next,还剩多少个东西
LL forward(LL x, int v) { return v < 26 ? (x - (x + 19) / 20) : (x - 1); }
// 至少要拿着多少个东西到达结点u,交税以后还能剩d[u]个东西
// 为了使代码容易理解,这里使用一种不太数学的解法
LL back(int u)
{
    if (u >= 26)
        return d[u] + 1;
    LL X = d[u] * 20 / 19;  // 初始值
    while (forward(X, u) < d[u])
        X++;  // 调整
    return X;
}

void Dijkstra(int s, int t, int p)
{
    int n = 52;  // 总是有52个结点
    memset(vis, 0, sizeof(vis));
    d[t] = p;
    vis[t] = true;
    for (int i = 0; i < n; i++)
        if (i != t)
            d[i] = G[i][t] ? back(t) : INF;
    // Dijkstra主过程,逆推
    while (!vis[s])
    {
        // 找最小的d
        int u = -1;
        for (int i = 0; i < n; i++)
            if (!vis[i] && (u < 0 || d[i] < d[u]))
                u = i;
        vis[u] = true;
        // 更新其他结点的d
        for (int i = 0; i < n; i++)
            if (!vis[i] && G[i][u])
                d[i] = min(d[i], back(u));
    }
}
int main()
{
    int n, kase = 0;
    while (~scanf("%d", &n) && (n + 1))
    {
        memset(G, 0, sizeof(G));
        for (int i = 0; i < n; i++)
        {
            int u = Read(), v = Read();
            if (u != v)
                G[u][v] = G[v][u] = true;
        }
        int p;
        scanf("%d", &p);
        int s = Read(), t = Read();
        printf("Case %d:\n", ++kase);
        Dijkstra(s, t, p);
        printf("%lld\n%c", d[s], alpha(s));
        LL x = d[s];
        for (int u = s, v; u != t; x = d[u = v], printf("-%c", alpha(v)))
            for (v = 0; v < 52; v++)  // 找到第一个可以走的结点
                if (G[u][v] && forward(x, v) >= d[v])
                    break;
        printf("\n");
    }
    return 0;
}
Last modification:July 3rd, 2019 at 02:30 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment