题解 UVA1599 【Ideal Path】
紫题
2018-11-03 20:52:56
## 题目大意：满足最短路的条件下，求出字典序最小的路径并输出
如果只是单纯的求最短路，对于这题只需要一遍dfs即可；输出具体路径也很简单，用$pre[i]$维护每个点的前驱节点就行了。
但是这题还要按照字典序输出，字典序和路径权值没有什么必然的关系，所以要先求出所有的最短路再考虑字典序的问题。 最小字典序只要一次BFS就可以找出来，后面会详细说。
我们知道，**单源最短路径**求出的是源点（起点）到所有点的最短路，其中会有一些路径并没有到达终点，我们要在求字典序的时候把这些无用的路径剔除
同样的，**单汇最短路径**求出的是汇点（终点）到所有点的最短路，其中会有一些路径并没有到达起点。**只要在这两种路径中取交集，剩下的就是起点到终点的最短路径。**
具体地来说，只要从起点跑一遍单源最短路（这题可以直接BFS），然后**建一个反图**（边的方向相反的图），然后从终点BFS一遍，看遍历到的哪些点在最短路径上即可
这题的边是无向边，所以省了建反图的功夫，在起点跑一遍单源最短路后直接从终点BFS一遍即可找出所有起点到终点的最短路了。
找到所有最短路后，就只剩寻找最小字典序了。可以从起点再来一次BFS，每一层扩展的时候**及时剔除字典序一定更大的节点**，保留当前字典序最小的节点用于下一次扩展就行了。
从最短路到字典序一共用了3次BFS，其实还可以做的更好：从终点开始求一次单源最短路，然后再从起点开始BFS，这样就可以在一次BFS中求出最短路的同时找出字典序最小的路径了。
$Code:$ （不卡常80ms）
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
int ver[400010],color[400010],first[100010],nxt[400010],cnt=1;
int que[400010],dis[100010],n,m;
bool vis[100010];
vector<int>ans;
void init(){ //初始化
memset(vis,0,sizeof(vis));
memset(first,0,sizeof(first));
memset(dis,-1,sizeof(dis));
ans.clear();
cnt=1;
}
void add(int x,int y,int z){ //加边
ver[++cnt]=y;color[cnt]=z;nxt[cnt]=first[x];first[x]=cnt;
}
void invbfs(){ //最短路
int head=0,tail=1;
que[0]=n,dis[n]=0; //一开始队列中只有终点
while(head!=tail){
int u=que[head];head++;
for(int k=first[u];k;k=nxt[k]){
int v=ver[k];
if(dis[v]!=-1) continue;
dis[v]=dis[u]+1;
que[tail++]=v;
}
}
}
void bfs(){
int head=0,tail=1;
que[0]=1;vis[1]=1; //一开始队列中只有起点
while(head!=tail){
vector<int>c;
while(head!=tail){ //将队列中的点全部取出到一个vector中
//这样做是方便在后续操作中将只字典序最小的节点放入队列扩展
c.push_back(que[head]);head++;
}
int minn=0x3f3f3f3f;
for(int i=0;i<(int)c.size();i++){
int u=c[i];
for(int k=first[u];k;k=nxt[k]){
int v=ver[k];
if(dis[v]+1==dis[u]) minn=min(color[k],minn);
//是最短路则记录最小字典序
}
}
if(minn==0x3f3f3f3f) return;
ans.push_back(minn);//压入答案序列中
for(int i=0;i<(int)c.size();i++){
int u=c[i];
for(int k=first[u];k;k=nxt[k]){
int v=ver[k];
if(dis[v]+1==dis[u]&&color[k]==minn&&!vis[v]){
//将在最短路上且字典序最小的节点放回队列中扩展
que[tail++]=v;
vis[v]=1;
}
}
}
}
}
void solve(){
init();
int x,y,z;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
invbfs();
bfs();
printf("%d\n",ans.size());
for(int i=0;i<(int)ans.size();i++) //输出路径
printf("%d%c",ans[i],i+1==(int)ans.size()?'\n':' ');
}
int main(){
while(scanf("%d%d",&n,&m)==2) solve(); //一开始没注意多组数据，WA哭了
return 0;
}
```