欢迎访问我的Uva题解目录哦 https://blog.****.net/ri*qi/article/details/81149109

题目描述

题意解析

给一个n个点m条边（$2≤n≤100000，1≤m≤200000$2≤n≤100000，1≤m≤200000）的无向图，每条边上都涂有一种颜色。求从结点1到结点n的一条路径，使得经过的边数尽量少，在此前提下，经过边的颜色序列的字典序最小。一对结点间可能有多条边，一条边可能连接两个相同结点。输入保证结点1可以达到结点n。颜色为$1～10^9$1～109的整数。

算法设计

借鉴《算法设计入门经典（第2版）》中的提示：

抛开字典序不谈，本题只是一个普通的最短路问题，可以用BFS解决。但是之前的“记录父结点”的方法已经不适用了，因为这样打印出来的路径并不能保证字典序最小。怎么办呢？
事实上，无须记录父结点也能得到最短路，方法是从终点开始“倒着”BFS，得到每个结点i到终点的最短距离d[i]，然后直接从起点开始走，但是每次到达一个新结点时要保证d值恰好减少1（如有多个选择则可以随便走），直到到达终点。可以证明（想一想，为什么）：这样走过的路径一定是一条最短路。
有了上述结论，本题就不难解决了：直接从起点开始按照上述规则走，如果有多种走法，选颜色字典序最小的走；如果有多条边的颜色字典序都是最小，则记录所有这些边的终点，走下一步时要考虑从所有这些点出发的边。聪明的读者应该已经看出来了：这实际上是又做了一次BFS，因此时间复杂度仍为O(m)。其实本题也可以只进行一次BFS，不过要从终点开始逆向进行，有兴趣的读者可以自行研究。

总结起来，就是先以结点n为起点，用BFS算法计算出结点n到达每一个结点的最短距离。然后以结点1为起点，再使用一次BFS算法找出最优路径。
具体实现可见代码。

注意点

本题中两个结点间可能有多条不同颜色的边。使用BFS算法注意要保证一个结点只能入队一次。

C++代码

#include<bits/stdc++.h>
using namespace std;
struct Edge{//边的类
    int v1,v2,color;
    Edge(int vv1,int vv2,int c):v1(vv1),v2(vv2),color(c) {}
};
const int MAX=100000;
int n,m,dis[MAX+5];
bool visit[MAX+5];
vector<Edge>edges;//存储每条边
vector<int>graph[MAX+5];//图
void revBFS(){//以顶点n为起点，计算出结点n到达每一个结点的最短距离
    memset(visit,0,sizeof(visit));
    queue<int>q;
    q.push(n);
    visit[n]=true;
    dis[n]=0;
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(int i:graph[t]){
            int v=(edges[i].v1==t)?edges[i].v2:edges[i].v1;//到达的顶点编号
            if(!visit[v]){
                visit[v]=true;
                q.push(v);
                dis[v]=dis[t]+1;
            }
        }
    }
}
void BFS(){//以结点1为起点，再使用一次BFS算法找出最优路径
    printf("%d\n",dis[1]);//输出最短路径长度
    memset(visit,0,sizeof(visit));
    visit[1]=true;
    vector<int>currentLevel;//当前最短距离下包含的顶点
    currentLevel.push_back(1);
    for(int j=0;j<dis[1];++j){
        int minColor=INT_MAX;//最小的颜色号
        for(int i:currentLevel){//遍历前当最短距离下包含的所有顶点
            for(int j:graph[i]){//遍历该顶点的所有边
                int v=(edges[j].v1==i)?edges[j].v2:edges[j].v1;
                if(dis[v]+1==dis[i])//到达的顶点是最短距离正好少1的点
                    minColor=min(minColor,edges[j].color);//更新minColor
            }
        }
        vector<int>nextLevel;//存储当前最短距离正好少1包含的所有顶点
        for(int i:currentLevel){
            for(int j:graph[i]){
                int v=(edges[j].v1==i)?edges[j].v2:edges[j].v1;
                if(!visit[v]&&dis[v]+1==dis[i]&&minColor==edges[j].color){
                    nextLevel.push_back(v);
                    visit[v]=true;
                }
            }
        }
        currentLevel=nextLevel;//转向处理最短距离正好少1包含的所有顶点
        printf("%d%s",minColor,j==dis[1]-1?"\n":" ");//输出颜色编号
    }
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        fill(graph+1,graph+n+1,vector<int>());
        edges.clear();
        int a,b,c;
        while(m--){
            scanf("%d%d%d",&a,&b,&c);
            graph[a].push_back(edges.size());
            graph[b].push_back(edges.size());
            edges.push_back(Edge(a,b,c));
        }
        revBFS();
        BFS();
    }
    return 0;
}