1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define MAXN 100016
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define inf 0x3f3f3f3f
#define cmx( a , b ) a = max( a , b )
#define cmn( a , b ) a = min( a , b )
int n , m;
int head[MAXN] , to[MAXN << 1] , wto[MAXN << 1] , nex[MAXN << 1] , ecn;
void ade( int u , int v , int w ) {
to[++ecn] = v , nex[ecn] = head[u] , wto[ecn] = w , head[u] = ecn;
}
int dis[MAXN] , len[MAXN] , pre[MAXN] , done[MAXN];
priority_queue<pii , vector<pii> , greater<pii> > Q;
queue<int> q;
void dijk( int s ) {
memset( dis , 0x3f , sizeof dis );
memset( len , 0x3f , sizeof len );
memset( pre , -1 , sizeof pre );
dis[s] = 0 , len[s] = 1;
q.push( s );
while( !q.empty() ) {
int u = q.front(); q.pop( );
for( int i = head[u] ; ~i ; i = nex[i] ) {
int v = to[i];
Q.push( mp( 0 , u ) );
if( dis[v] && ! wto[i] )
q.push( v ) , dis[v] = 0 , pre[v] = ( i ^ 1 ) , len[v] = len[u] + 1;
}
}
int rnk = 0 , last = -1;
while( !Q.empty() ) {
pii too = Q.top( ); Q.pop( );
int u = too.se;
if( done[u] ) continue;
done[u] = true;
if( last != dis[u] ) last = dis[u] , ++ rnk;
for( int i = head[u] ; ~i ; i = nex[i] ) {
int v = to[i];
if( dis[v] > rnk * 10 + wto[i] ) {
dis[v] = rnk * 10 + wto[i];
pre[v] = ( i ^ 1 );
len[v] = len[u] + 1;
Q.push( mp( dis[v] , v ) );
} else if( dis[v] == rnk * 10 + wto[i] && len[v] > len[u] + 1 ) {
pre[v] = ( i ^ 1 );
len[v] = len[u] + 1;
Q.push( mp( dis[v] , v ) );
}
}
}
}
int main() {
memset( head , -1 , sizeof head ) , ecn = -1;
cin >> n >> m;
for( int i = 1 , u , v , w ; i <= m ; ++ i ) {
scanf("%d%d%d",&u,&v,&w);
++ u , ++ v;
ade( u , v , w ) , ade( v , u , w );
}
dijk( n );
int c = 1;
stack<int> sss;
while( c != n )
sss.push( wto[pre[c]] ) , c = to[pre[c]];
while( !sss.empty() && sss.top() == 0 ) sss.pop();
if( sss.empty() ) printf("0");
else while( !sss.empty() ) printf("%d",sss.top()) , sss.pop();
puts("");
printf("%d\n" , len[1]);
c = 1;
printf("%d ",0);
while( c != n )
c = to[pre[c]] , printf("%d ",c - 1);
}
|
