UVA 10537 Toll! Revisited ( PFS )

UVa Online Judge
從終點逆推回去更新最小值。具體來說用 Priority First Search，尋找目前還沒用過的擁有最小值的節點來更新它所有可能的前驅點。打印路徑的時候只要反方向( 其實也就是順向 ) 檢查哪些點是可通行的，取其字典序最小慢慢遞進就行了。複雜度不太會估，大概 O( V * V * lg E ) 吧。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
const int MAXN = 60 + 2;
const ll INF = 1LL << 60;

int kase;
int n, m;
vector<int> G[MAXN];
int src, gol, p;

int readPlace(){
    char buf[10]; scanf("%s", buf);
    if( 'A' <= buf[0] && buf[0] <= 'Z' ) return buf[0] - 'A';
    return buf[0] - 'a' + 26;
}
char toPlace(int u){
    if( u < 26 ) return 'A' + u;
    return 'a' + u - 26;
}

int vis[MAXN];
ll need[MAXN];
ll fcost(ll cnt, int v){ // move things toward goal
    if( v >= 26 ) return cnt - 1;
    return cnt - ( cnt + 19 ) / 20; // upper gauss
}
ll bcost(int u){ // minimum requirment for previous
    if( u >= 26 ) return need[ u ] + 1;
    ll res = need[ u ] * 20 / 19;
    while( fcost( res, u ) < need[ u ] ) ++res;
    return res;
}
void pfs(int s){
    memset( vis, 0, sizeof(vis) );
    fill( need, need + MAXN, INF );
    need[ s ] = p;
    priority_queue<pli, vector<pli>, greater<pli> > pq;
    pq.push( pli( need[ s ], s ) );
    vis[ s ] = 1;
    while( !pq.empty() ){
        int u = pq.top().second; pq.pop();
        for(int i = 0; i < G[u].size(); ++i){
            int v = G[u][i];
            if( need[ v ] > bcost( u ) ){
                need[ v ] = bcost( u );
                if( vis[ v ] ) continue;
                vis[ v ] = 1;
                pq.push( pli( need[ v ], v ) );
            }
        }
    }
}

void solve(){
    n = 52; // [ 0, 52 ) <=> [ a, Z ]
    pfs( gol );
    printf("%lld\n", need[ src ]);
    printf("%c", toPlace( src ));
    ll cnt = need[ src ];
    for(int u = src, v; u != gol; u = v){
        v = 100;
        for(int i = 0; i < G[u].size(); ++i){
            int k = G[u][i];
            if( fcost( cnt, k ) >= need[ k ] )
                v = min( v, k ); // lexicographically
        }
        cnt = need[ v ];
        printf("-%c", toPlace( v ));
    }
    puts("");
}

void init(){
    for(int i = 0; i < MAXN; ++i)
        G[i].clear();
}

int main(){
    while( scanf("%d", &n) == 1 && n >= 0 ){
        init();
        for(int i = 0; i < n; ++i){
            int u = readPlace();
            int v = readPlace();
            if( u == v ) continue;
            G[ u ].push_back( v );
            G[ v ].push_back( u );
        }
        scanf("%d", &p);
        src = readPlace();
        gol = readPlace();
        printf("Case %d:\n", ++kase);
        solve();
    }
    return 0;
}