题目链接
题意：给定一个无向图，大写字母是城市，小写字母是村庄，经过城市交过路费为当前货物的%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 = 105;
const long long Inf = (1LL<<61);
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[255];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=0; 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-1);}void print(int u){if( p[u]==-1 ){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=0; i<n; i++ ) d[i]=Inf, done[i]=0;d[s]=vl;p[s]=-1;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]=1;for ( int i=0; i<G[u].size(); i++ ){Edge& e=edges[G[u][i]];long long nd;if( e.w ) nd= (long long) ceil(d[u]*1.0/19*20);else nd=d[u]+1;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=0; 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-1);}void print(int u){if( p[u]==-1 ){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=0; i<n; i++ ) d[i]=Inf, inq[i]=0;d[s]=vl;p[s]=-1;queue<int> Q;Q.push(s);while( !Q.empty() ){int u=Q.front(); Q.pop();inq[u]=0;for ( int i=0; i<G[u].size(); i++ ){Edge& e=edges[G[u][i]];long long nd;if( e.w ) nd=(long long) ceil(d[u]*1.0/19*20);else nd=d[u]+1;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]=1;Q.push(e.v);}}}}}
};
SPFA D;
int vis[255];
int main(){for ( int i=0; i<26; i++ ) {vis['a'+i]=i+26; to[i+26]='a'+i;vis['A'+i]=i; to[i]='A'+i;}int n, m, kas=0;while( scanf("%d", &m ) == 1 && m!=-1 ){D.init(52);char a[2], b[2];for ( int i=1; i<=m; i++ ){scanf("%s%s", a, b );int u=vis[a[0]], v=vis[b[0]];D.addeage(u,v,a[0]<'a');D.addeage(v,u,b[0]<'a');}long long vl;scanf("%lld%s%s", &vl, a, b );int u=vis[a[0]], v=vis[b[0]];D.spfa(v,vl);printf("Case %d:\n", ++kas); printf("%lld\n", D.d[u]); D.print(u);}
}