问题描述：
给出n和m，有n个点，m条双向边，1为起点，n为终点，每条边都有一个权值，经过每一条边的时间都为1，求从起点到终点既要时间最少，又要权值组成的序列的字典序最小的一条路径.
输入样例：
4 6 1 2 1 1 3 2 3 4 3 2 3 1 2 4 4 3 1 1
输出样例：
2 1 3
限制范围：
50%,n<=100 100%,n<=100000,m<=200000
分析：
又是一道双关键字限制结果最优性的问题，此类问题一般思路就是枚举一个，计算最优另一个。 对于这道题，我们可以先用SPFA算出从终点开始到每个点的距离，然后从起点开始，每一步都选择权值最小的即可。其实也不是很复杂。
参考程序：
#include<cstdio>
#include<algorithm>
#include<set>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=610000;
const int INF=0x3f3f3f3f;
struct Edge{
int j,v,next;
}e[maxn];
int EdgeCnt=0;
int d[maxn],a[maxn];
bool inq[maxn];
queue<int> Q;
int n,m;
void addedge(int u,int v,int w){
int p=++EdgeCnt;
e[p].j=v;e[p].v=w;e[p].next=a[u];
a[u]=p;
}
int main(){
freopen("ideal.in","r",stdin);
freopen("ideal.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=0;i<m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
memset(d,0x3f,sizeof(d));
Q.push(n);
inq[n]=true;
d[n]=0;
while (!Q.empty()){
int u=Q.front();Q.pop();
for (int p=a[u];p;p=e[p].next){
int j=e[p].j;
if (d[j]>d[u]+1){
d[j]=d[u]+1;
if (!inq[j]){
inq[j]=true;
Q.push(j);
}
}
}
inq[u]=false;
}
printf("%d\n",d[1]);
set<int> now,next;
now.insert(1);
for (int dist=d[1]-1;dist>=0;dist--){
int col=INF;
for (set<int>::iterator u=now.begin();u!=now.end();u++){
for (int p=a[*u];p;p=e[p].next){
int j=e[p].j,v=e[p].v;
if (d[j]==dist && v<=col){
if (v<col){
col=v;
next.clear();
next.insert(j);
}else if (next.find(j)==next.end())next.insert(j);
}
}
}
printf("%d ",col);
now=next;next.clear();
}
return 0;
}