#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std
;
#define INF 0x7FFFFFFF
typedef struct
{ int w
, adj
; }Arcnode
;
vector
<vector
<Arcnode
>> G
;
vector
<int > Path
, nPath
, Dist
, visited
, cnt
;
bool SPFA( int v
, int N
)
{
queue
<int > q
;
q
.push(v
);
visited
[v
] = 1;
++cnt
[v
];
while( !q
.empty() )
{
v
= q
.front();
q
.pop();
visited
[v
] = 0;
for( int i
= 0; i
< G
[v
].size(); ++i
)
if( Dist
[v
] != INF
&& Dist
[ G
[v
][i
].adj
] > Dist
[v
] + G
[v
][i
].w
)
{
Dist
[ G
[v
][i
].adj
] = Dist
[v
] + G
[v
][i
].w
;
nPath
[ G
[v
][i
].adj
] = nPath
[v
];
Path
[ G
[v
][i
].adj
] = v
;
if( !visited
[ G
[v
][i
].adj
] )
{
q
.push( G
[v
][i
].adj
);
visited
[ G
[v
][i
].adj
] = 1;
if( ++cnt
[ G
[v
][i
].adj
] >= N
)
return false;
}
}
else if( Dist
[v
] != INF
&& Dist
[ G
[v
][i
].adj
] == Dist
[v
] + G
[v
][i
].w
)
nPath
[ G
[v
][i
].adj
] += nPath
[v
];
}
return true;
}
int main()
{
int N
, M
, V1
, V2
, a
, b
, w
;
Arcnode temp
;
scanf("%d %d %d %d", &N
, &M
, &V1
, &V2
);
Path
.resize(N
);
Dist
.resize(N
);
nPath
.resize(N
);
visited
.resize(N
);
cnt
.resize(N
);
visited
.resize(N
);
G
.resize(N
);
fill( Dist
.begin(), Dist
.end(), INF
);
fill( Path
.begin(), Path
.end(), -1 );
Dist
[V1
] = 0;
nPath
[V1
] = 1;
for( int i
= 0; i
< M
; ++i
)
{
scanf("%d %d %d", &a
, &temp
.adj
, &temp
.w
);
G
[a
].push_back( temp
);
}
if( SPFA( V1
, N
) )
{
for( int i
= 0; i
< N
; ++i
)
printf("%d%s", Dist
[i
], i
== N
- 1 ? "\n":" ");
for( int i
= V2
; i
!= -1; i
= Path
[i
] )
printf("%d ", i
);
printf("\n%d", nPath
[V2
]);
}
}
测试用例：给点节点数与路径数， 给定任意两存在节点，输出最短距离，及最短路径
6 8 0 2
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1
3 2 2
3 4 3
4 5 3
