<题目链接>
题目大意：
给你一张图，有n个点，每个点都有需要缴的税，两个直接相连点之间的道路也有需要花费的费用。现在进行多次询问，给定起点和终点，输出给定起点和终点之间最少花费是多少，并且输出最少花费所走的路径，如果有多条路径花费最少，则输出字典序最小的那条。
解题分析：
输出最短路的路径问题，需要注意的是，题目要求输出的最短路径的字典序最小，所以我们在每次松弛的时候，都需要加上判断。如果有多个点的最短路相同，则用DFS求出它们之前走过的路径，并且进行比较，然后选字典序最小的那条。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std; #define clr(a,b) memset(a,b,sizeof(a))
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define INF 0x3f3f3f3f
const int M = +;
int n,pos;
int path[M],mp[M][M],tax[M],vis[M],dis[M];
char s1[],s2[];
void dfs(int cur,char *s){ //找到这个点之前记录的路径s
if(cur == -)return;
dfs(path[cur],s);
s[pos++]=cur+'';
}
bool Compare(int re,int now) {
pos=;dfs(re,s1);s1[pos] = ''; //将起点到re的最短路径储存
pos=;dfs(now,s2);s2[pos++]=re+'';s2[pos]=; //将起点到u的最短路径储存
if(strcmp(s1,s2)>)return true; //比较两个最短路之间的大小
return false;
}
void Dij(int st,int ed){
rep(i,,n){
dis[i]=mp[st][i]+tax[i]; //将与st直接相连的点，边权与点权相加，视为经过i号城市的代价
if(i==st)continue;
if(dis[i]<INF)path[i]=st; //初始化path
}
rep(i,,n){
int mn=INF,cur;
rep(j,,n) if(dis[j] < mn && !vis[j]) { //找到每一轮的起始节点
mn=dis[j],cur=j;
}vis[cur]=;
rep(k,,n) if(mp[cur][k] < INF){
if(dis[k]>dis[cur]+mp[cur][k]+tax[k]){ //进行松弛，并且记录上一个节点
dis[k]=dis[cur]+mp[cur][k]+tax[k];
path[k]=cur;
}else if(dis[k] == dis[cur]+mp[cur][k]+tax[k] && Compare(k,cur)){
path[k]=cur;
}//若有多条最短路径(最短距离相同的时候)进行字典序大小判断，注意不能只比较一个节点，需要比较整个路径
}
}
}
void show(int cur,int st){
if(cur == st){ cout<<cur; return ;}
show(path[cur],st);
cout<<"-->"<<cur;
}
int main(){
while(~scanf("%d",&n),n){
rep(i,,n) rep(j,,n){
scanf("%d",&mp[i][j]);
if(mp[i][j]==-)mp[i][j]=INF;
}
rep(i,,n)scanf("%d",&tax[i]);
int u,v;while(scanf("%d%d",&u,&v)){
if(u==- && v==-)break;
clr(vis,);clr(path,-);
Dij(u,v);
cout<<"From "<<u<<" to "<<v<<" :"<<endl<<"Path: ";
show(v,u);puts(""); //从终点开始,利用递归，将逆序存储的路径正序输出
cout<<"Total cost : "<<dis[v]-tax[v]<<endl<<endl; //减去终点城市的城市税
}
}
}
2018-12-06