UVA 10537 The Toll! Revisited（最短路變形）

從s到t，每次經過一個村莊要繳納1個單位的貨物，經過一個城鎮時，每20個貨物就要繳納一個，求字典序最小的最少花費路徑。

用最短路的思想來解。從終點跑最短路，對於邊<u, v>的邊權值，如果u是村莊，邊權自然是1，當u是城鎮時，邊權是min{key | key - (key+19)/20=d[u]}。

求出最短路後，從起始點dfs，每次沿著滿足最距離且字典序最小的邊走就OK了~

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<fstream>
#include<sstream>
#include<string>
#include<vector>
#include<cstdio>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define PB push_back
#define LL long long
using namespace std;

LL bin(LL k) //二分查找路過城鎮前所需最少貨物
{
    LL L=0, R=k*2+1, M, ans;
    while(L <= R)
    {
        M = (L + R) >> 1;
        LL tmp = M - (M + 19) / 20;
        if(tmp > k) R = M - 1;
        else if(tmp == k) ans = M, R = M - 1;
        else L = M + 1;
    }
    return ans;
}

const int maxn = 111;
const LL INF = 10000000000;
int n, m, s, t;
string name, ans;
struct heap
{
    LL d;
    int u;
    bool operator<(const heap rhs) const
    {
        return d > rhs.d;
    }
};
vector<int> G[maxn];
bool done[maxn];
LL d[maxn], P;
map<char, int> id;

inline void init()
{
    REP(i, maxn) G[i].clear();
    n = 0; name.clear(); ans.clear(); id.clear();
}

int get(char c)
{
    if(!id.count(c)) id[c] = n++, name.PB(c);
    return id[c];
}

void dij(int s)
{
    REP(i, n) d[i] = INF; d[s] = P;
    priority_queue<heap> q; q.push((heap){0, s});
    CLR(done, 0);
    while(!q.empty())
    {
        heap x = q.top(); q.pop();
        int nc = G[x.u].size(), u = x.u;
        if(done[u]) continue;
        done[u] = 1;
        REP(i, nc)
        {
            int v = G[u][i];
            LL tmp = d[u] + 1;
            if(isupper(name[u])) tmp = bin(d[u]);//邊權
            if(d[v] > tmp)
            {
                d[v] = tmp;
                q.push((heap){d[v], v});
            }
        }
    }
}

void dfs(int u)
{
    if(u == t) return ;
    char c = 'z';
    int nc = G[u].size();
    REP(i, nc)
    {
        int v = G[u][i];
        LL tmp = d[u] - 1;
        if(isupper(name[v])) tmp = d[u] - (d[u] + 19) / 20;
        if(d[v] == tmp) if(name[v] <= c) c = name[v]; //走字典序最小的路徑
    }
    ans.PB(c);
    dfs(id[c]);
}

int main()
{
    int kase = 1;
    while(scanf("%d", &m), m != -1)
    {
        init();
        char a[2], b[2];
        while(m--)
        {
            scanf("%s%s", a, b);
            int aa = get(a[0]), bb = get(b[0]);
            G[aa].PB(bb), G[bb].PB(aa);
        }
        scanf("%lld %s%s", &P, a, b);
        s = get(a[0]), t = get(b[0]);

        dij(t);

        ans.PB(a[0]);
        dfs(s);

        printf("Case %d:\n", kase++);
        printf("%lld\n", d[s]);
        int nc = ans.size();
        REP(i, nc) printf("%c%c", ans[i], i == nc-1 ? '\n' : '-');
    }
    return 0;
}