题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3760
思路:首先是建反图,从点n开始做spfa求出n到各点的最短路,然后从1点开始搜最小序列,对于边(u,v),若dist[u]==dist[v]+1,则要将当前的序号加入当前队列中,然后就是对于那些序号相同点的都要加入当前队列,还要判一下重。至于为什么要建反图从n点开始求最短路,因为在搜最小序列的时候要保证一定能搜到n点。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 1000000
#define inf 1<<30 struct Edge{
int v,w,color,next;
}edge[MAXN]; int n,m,NE;
int head[MAXN]; void Insert(int u,int v,int w,int color)
{
edge[NE].v=v;
edge[NE].w=w;
edge[NE].color=color;
edge[NE].next=head[u];
head[u]=NE++;
} bool mark[MAXN];
int dist[MAXN];
void spfa()
{
memset(mark,false,sizeof(mark));
fill(dist,dist+MAXN,inf);
dist[n]=;
queue<int>que;
que.push(n);
while(!que.empty()){
int u=que.front();
que.pop();
mark[u]=false;
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v,w=edge[i].w;
if(dist[u]+w<dist[v]){
dist[v]=dist[u]+w;
if(!mark[v]){
mark[v]=true;
que.push(v);
}
}
}
}
} int vv[MAXN];
void BFS()
{
memset(mark,false,sizeof(mark));
queue<int>que;
que.push();
int flag=;
while(!que.empty()){
int num=,ans=inf;
int u=que.front();
if(u==n)break;
int size=que.size();
while(size--){
u=que.front();
que.pop();
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].v,w=edge[i].w,color=edge[i].color;
if(dist[u]==dist[v]+w){
if(color<ans){
ans=color;
num=;
vv[num++]=v;
}else if(color==ans){
vv[num++]=v;
}
}
}
}
if(flag){
printf("%d",ans);
flag=;
}else
printf(" %d",ans);
for(int i=;i<num;i++){
if(mark[vv[i]])continue;
mark[vv[i]]=true;
que.push(vv[i]);
}
}
puts("");
} int main()
{
int _case,u,v,color;
scanf("%d",&_case);
while(_case--){
scanf("%d%d",&n,&m);
NE=;
memset(head,-,sizeof(head));
while(m--){
scanf("%d%d%d",&u,&v,&color);
Insert(u,v,,color);
Insert(v,u,,color);
}
spfa();
printf("%d\n",dist[]);
BFS();
}
return ;
}