每经过一个城市速度会慢十倍,每个城市的距离是0---9,要求从0到n-1时间最短,时间相同的情况下,经过城市最少,输出时间,经过城市,还有路径
首先从n-1bfs搜索所有的含有前导0的城市,再从0点bfs搜索到有前导0的城市中距离最短的长度len,再从所有长度为len且还有前导0的城市开始bfs,每次找一条最短的边,直到0点
#include <bits/stdc++.h>
const int N=2e5+10;
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int> ii;
typedef vector<ii> vii;
int n,m;
vii v[N];
int zero[N];
int q[N];
int prev[N];
int dep[N];
void init_zero(int x){
zero[x]=1;
int l=0,r=1;
q[0]=x;
dep[x]=0;
while(l<r){
int u=q[l++];
for(int i=0;i<v[u].size();i++){
int z=v[u][i].fi,w=v[u][i].se;
if(w==0 && !zero[z]){
dep[z]=dep[u]+1;
zero[z]=1;
q[r++]=z;
prev[z]=u;
}
}
}
}
int len;
int d[N];
int vis[N];
int add;
void find_len(){
d[0]=0;
int l=0,r=1;
q[0]=0;
vis[0]=1;
len=1e9;
add=0;
while(l<r){
int u=q[l++];
if(zero[u]) {
if(d[u]<len) len=d[u],add=u;
}
for(int i=0;i<v[u].size();i++){
int z=v[u][i].fi;
if(!vis[z]){
vis[z]=1;
d[z]=d[u]+1;
q[r++]=z;
}
}
}
}
int tq[N];
int cnt;
void out(int x){
if(x==n-1){
printf("%d\n",x);
return;
}
printf("%d ",x);
out(prev[x]);
}
void solve(){
int tot=0;
rep(i,n) if(zero[i] && d[i]==len) q[tot++]=i;
for(int t=len;t;t--){
int mi=10;
rep(i,tot){
int u=q[i];
rep(j,v[u].size()) {
int z=v[u][j].fi,w=v[u][j].se;
if(d[u]==d[z]+1) mi=min(mi,w);
}
}
cnt=0;
rep(i,tot){
int u=q[i];
rep(j,v[u].size()){
int z=v[u][j].fi,w=v[u][j].se;
if(d[u]==d[z]+1 && w==mi) {
tq[cnt++]=z;
prev[z]=u;
if(dep[z]==0 || dep[z]>dep[u]+1) dep[z]=dep[u]+1;
}
}
}
rep(i,cnt) q[i]=tq[i];tot=cnt;
printf("%d",mi);
}
if(zero[0]) printf("0");
puts("");
printf("%d\n",dep[0]+1);
out(0);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("aaa","r",stdin);
#endif
scanf("%d%d",&n,&m);
rep(i,m){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
v[a].pb(mp(b,c));
v[b].pb(mp(a,c));
}
init_zero(n-1);
find_len();
// cout<<len<<endl;
solve();
return 0;
}