UVA10537[The Toll! Revisited] dijkstra/spfa 反向建图

题目链接

题意：给定一个无向图，大写字母是城市，小写字母是村庄，经过城市交过路费为当前货物的%5，路过村庄固定交1，给定起点终点和到目标地点要剩下的货物，问最少要带多少货物上路，并输出路径，如果有多种方案，要求字典序最小

solution：反向建图， d[i]表示从i到终点需要的数量。

#include <map>
#include <cmath>
#include <queue>
#include <vector> 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = ;
const long long Inf = (L<<);
struct Edge{
    int u, v, w;
    Edge(int u, int v, int w):u(u),v(v),w(w){}
}; 
struct HeapNode{
    long long d;int u;
    bool operator<(const HeapNode& rhs) const{
        return d>rhs.d;
    }
};

char to[];

struct Dijkstra{
    int n, m;
    long long d[N];
    bool done[N];
    vector<Edge> edges;
    vector<int> G[N];
    int p[N];
    void init(int n){
        this->n=n;
        for ( int i=; i<n; i++ ) G[i].clear();
        edges.clear(); 
    }
    void addeage(int u, int v, int w){
        edges.push_back((Edge){u,v,w});
        m=edges.size();
        G[u].push_back(m-);
    }
    void print(int u){
        if( p[u]==- ){
            printf("%c\n", to[u]);
            return;
        }
        printf("%c-", to[u] );
        print(edges[p[u]].u);
    }
    void dijkstra(int s, long long vl){
        for ( int i=; i<n; i++ ) d[i]=Inf, done[i]=;
        d[s]=vl;
        p[s]=-;
        priority_queue<HeapNode> Q;
        Q.push((HeapNode){vl,s});
        while( !Q.empty() ){
            HeapNode x=Q.top(); Q.pop();
            int u=x.u;
            if( done[u] ) continue;
            done[u]=;
            for ( int i=; i<G[u].size(); i++ ){
                Edge& e=edges[G[u][i]];
                long long nd;
                if( e.w ) nd= (long long) ceil(d[u]*/*);
                else nd=d[u]+;
                if( d[e.v]>nd || d[e.v]==nd && to[u]<to[edges[p[e.v]].u] ){
                    d[e.v]=nd;
                    p[e.v]=G[u][i];
                    Q.push((HeapNode){d[e.v],e.v});
                }
            }
        }

    }
};

struct SPFA{
    int n, m;
    long long d[N];
    bool inq[N];
    int p[N];
    vector<Edge> edges;
    vector<int> G[N];
    void init(int n){
        this->n=n;
        for ( int i=; i<n; i++ ) G[i].clear();
        edges.clear();
    }
    void addeage(int u, int v, int w){
        edges.push_back((Edge){u,v,w});
        m=edges.size();
        G[u].push_back(m-);
    }
    void print(int u){
        if( p[u]==- ){
            printf("%c\n", to[u] );
            return ;
        }
        printf("%c-", to[u] );
        print(edges[p[u]].u);
    }
    void spfa(int s, long long vl){
        for ( int i=; i<n; i++ ) d[i]=Inf, inq[i]=;
        d[s]=vl;
        p[s]=-;
        queue<int> Q;
        Q.push(s);
        while( !Q.empty() ){
            int u=Q.front(); Q.pop();
            inq[u]=;
            for ( int i=; i<G[u].size(); i++ ){
                Edge& e=edges[G[u][i]];
                long long nd;
                if( e.w ) nd=(long long) ceil(d[u]*/*);
                else nd=d[u]+;
                if( d[e.v]>nd || d[e.v]==nd && to[u]<to[edges[p[e.v]].u] ){
                    d[e.v]=nd;
                    p[e.v]=G[u][i];
                    if( !inq[e.v] ){
                        inq[e.v]=;
                        Q.push(e.v);
                    }
                }
            }
        }
    }
};
SPFA D;
int vis[];
int main(){
    for ( int i=; i<; i++ ) {
        vis['a'+i]=i+; to[i+]='a'+i;
        vis['A'+i]=i; to[i]='A'+i;
    }
    int n, m, kas=;
    while( scanf("%d", &m ) ==  && m!=- ){
        D.init();
        char a[], b[];
        for ( int i=; i<=m; i++ ){
            scanf("%s%s", a, b );
            int u=vis[a[]], v=vis[b[]];
            D.addeage(u,v,a[]<'a');
            D.addeage(v,u,b[]<'a');
        }
        long long vl;
        scanf("%lld%s%s", &vl, a, b );
        int u=vis[a[]], v=vis[b[]];
        D.spfa(v,vl);
        printf("Case %d:\n", ++kas);  
        printf("%lld\n", D.d[u]);  
        D.print(u);
    }
}