UVA10537 The Toll! Revisited

[vjudge]https://cn.vjudge.net/problem/UVA-10537

记(dis_i)为从(i)到(ed)最少需要多少单位的货物，这个东西可以直接dijkstra，初始条件(dis_{ed}=x)

输出方案的话直接从(st)开始找，每次找下一个点(nxt)时都要满足(dis_{now}-cost_{nxt}==dis_{nxt})且(nxt)的字典序最小

唯一需要注意的是在做最短路的时候，由于我们这个过程是一个逆推的过程（即知道后继要求前面的点），这一部分的(cost)应该除以(19)而不是(20)

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd (ll)1e18
#define eps 1e-8
int n,m,mp[300];
ll dis[60],lim;
bool vis[60];
vector<int> sq[60];
char s[10],t[10];

int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

void dij(int st,int ed,int lim)
{
	rep(i,1,n) dis[i]=maxd;
	dis[ed]=lim;
	memset(vis,0,sizeof(vis));
	rep(p,1,n)
	{
		int best=0;ll mind=maxd;
		rep(i,1,n) 
			if ((!vis[i]) && (dis[i]<mind)) {mind=dis[i];best=i;}
		if (mind==maxd) return;
		vis[best]=1;
		int len=sq[best].size();
		rep(i,0,len-1)
		{
			int v=sq[best][i];ll cost;
			if (best<27) cost=ceil((double)dis[best]/19.0);
			else cost=1;
			if ((dis[v]>dis[best]+cost) && (!vis[v]))
				dis[v]=dis[best]+cost;
		}
	}
}

int main()
{
	rep(i,1,26) mp['A'+i-1]=i;
	rep(i,1,26) mp['a'+i-1]=i+26;n=52;
	int cas=0;
	while ((scanf("%d",&m)==1) && (m!=-1))
	{
		rep(i,1,n) sq[i].clear();
		rep(i,1,m)
		{
			scanf("%s%s",s+1,t+1);
			int u=mp[s[1]],v=mp[t[1]];
			sq[u].pb(v);sq[v].pb(u);
		}
		scanf("%lld%s%s",&lim,s+1,t+1);
		int st=mp[s[1]],ed=mp[t[1]];
		//cout << st << " " << ed << endl;
		dij(st,ed,lim);
		//rep(i,1,n) cout << dis[i] << " ";cout << endl;
		printf("Case %d:
%lld
",++cas,dis[st]);
		putchar(s[1]);
		int now=st;
		while (now!=ed)
		{
			int len=sq[now].size(),best=100;
			rep(i,0,len-1)
			{
				int v=sq[now][i],cost;
				if (v<27) cost=ceil((double)dis[now]/20);
				else cost=1;
				if ((dis[now]-cost==dis[v]) && (v<best)) best=v;
			}
			now=best;putchar('-');
			if (now<27) putchar('A'+now-1);else putchar('a'+now-27);
		}
		puts("");
	}
	return 0;
}