1 介绍
本专题用来记录使用。。。。
2 训练
题目1 :1137选择最佳线路
C++代码如下,
# include <iostream>
# include <cstring>
# include <algorithm>
# include <queue>
using namespace std;
const int N = 1010 , M = 20010 ;
int n, m;
int dist[ N] ;
int st[ N] ;
vector< vector< pair< int , int >> > g;
vector< int > snodes;
int enode;
int w;
void spfa ( ) {
memset ( dist, 0x3f , sizeof dist) ;
memset ( st, 0 , sizeof st) ;
queue< int > q;
for ( auto snode : snodes) {
dist[ snode] = 0 ;
q. push ( snode) ;
st[ snode] = true ;
}
while ( ! q. empty ( ) ) {
auto t = q. front ( ) ;
q. pop ( ) ;
st[ t] = false ;
for ( auto [ b, w] : g[ t] ) {
if ( dist[ b] > dist[ t] + w) {
dist[ b] = dist[ t] + w;
if ( ! st[ b] ) {
q. push ( b) ;
st[ b] = true ;
}
}
}
}
return ;
}
int main ( ) {
while ( cin >> n >> m >> enode) {
g. clear ( ) ;
g. resize ( n + 10 ) ;
for ( int i = 0 ; i < m; ++ i) {
int a, b, c;
cin >> a >> b >> c;
g[ a] . emplace_back ( b, c) ;
}
cin >> w;
snodes. resize ( w) ;
for ( int i = 0 ; i < w; ++ i) cin >> snodes[ i] ;
spfa ( ) ;
if ( dist[ enode] == 0x3f3f3f3f ) cout << "-1" << endl;
else cout << dist[ enode] << endl;
}
return 0 ;
}
题目2 :1131拯救大兵瑞恩
C++代码如下,
# include <cstring>
# include <iostream>
# include <algorithm>
# include <deque>
# include <set>
# define x first
# define y second
using namespace std;
typedef pair< int , int > PII;
const int N = 11 , M = 360 , P = 1 << 10 ;
int n, m, k, p;
int h[ N * N] , e[ M] , w[ M] , ne[ M] , idx;
int g[ N] [ N] , key[ N * N] ;
int dist[ N * N] [ P] ;
bool st[ N * N] [ P] ;
set< PII> edges;
void add ( int a, int b, int c) {
e[ idx] = b, w[ idx] = c, ne[ idx] = h[ a] , h[ a] = idx++ ;
}
void build ( ) {
int dx[ 4 ] = { - 1 , 0 , 1 , 0 } , dy[ 4 ] = { 0 , 1 , 0 , - 1 } ;
for ( int i = 1 ; i <= n; ++ i) {
for ( int j = 1 ; j <= m; ++ j) {
for ( int u = 0 ; u < 4 ; ++ u) {
int x = i + dx[ u] , y = j + dy[ u] ;
if ( ! x || x > n || ! y || y > m) continue ;
int a = g[ i] [ j] , b = g[ x] [ y] ;
if ( ! edges. count ( { a, b} ) ) add ( a, b, 0 ) ;
}
}
}
return ;
}
int bfs ( ) {
memset ( dist, 0x3f , sizeof dist) ;
dist[ 1 ] [ 0 ] = 0 ;
deque< PII> q;
q. push_back ( { 1 , 0 } ) ;
while ( q. size ( ) ) {
PII t = q. front ( ) ;
q. pop_front ( ) ;
if ( st[ t. x] [ t. y] ) continue ;
st[ t. x] [ t. y] = true ;
if ( t. x == n * m) return dist[ t. x] [ t. y] ;
if ( key[ t. x] ) {
int state = t. y | key[ t. x] ;
if ( dist[ t. x] [ state] > dist[ t. x] [ t. y] ) {
dist[ t. x] [ state] = dist[ t. x] [ t. y] ;
q. push_front ( { t. x, state} ) ;
}
}
for ( int i = h[ t. x] ; ~ i; i = ne[ i] ) {
int j = e[ i] ;
if ( w[ i] && ! ( t. y >> w[ i] - 1 & 1 ) ) continue ;
if ( dist[ j] [ t. y] > dist[ t. x] [ t. y] + 1 ) {
dist[ j] [ t. y] = dist[ t. x] [ t. y] + 1 ;
q. push_back ( { j, t. y} ) ;
}
}
}
return - 1 ;
}
int main ( ) {
cin >> n >> m >> p >> k;
for ( int i = 1 , t = 1 ; i <= n; ++ i) {
for ( int j = 1 ; j <= m; ++ j) {
g[ i] [ j] = t++ ;
}
}
memset ( h, - 1 , sizeof h) ;
while ( k-- ) {
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
int a = g[ x1] [ y1] , b = g[ x2] [ y2] ;
edges. insert ( { a, b} ) , edges. insert ( { b, a} ) ;
if ( c) add ( a, b, c) , add ( b, a, c) ;
}
build ( ) ;
int s;
cin >> s;
while ( s-- ) {
int x, y, c;
cin >> x >> y >> c;
key[ g[ x] [ y] ] |= 1 << c - 1 ;
}
cout << bfs ( ) << endl;
return 0 ;
}
题目3 :1134最短路计数
C++代码如下,
# include <iostream>
# include <cstring>
# include <algorithm>
# include <vector>
# include <queue>
using namespace std;
const int N = 1e5 + 10 , mod = 100003 ;
int n, m;
vector< vector< int >> g;
int dist[ N] ;
int cnt[ N] ;
void bfs ( ) {
memset ( dist, 0x3f , sizeof dist) ;
queue< int > q;
q. push ( 1 ) ;
cnt[ 1 ] = 1 ;
dist[ 1 ] = 0 ;
while ( ! q. empty ( ) ) {
auto t = q. front ( ) ;
q. pop ( ) ;
for ( auto b : g[ t] ) {
if ( dist[ b] > dist[ t] + 1 ) {
dist[ b] = dist[ t] + 1 ;
cnt[ b] = cnt[ t] ;
q. push ( b) ;
} else if ( dist[ b] == dist[ t] + 1 ) {
cnt[ b] = ( cnt[ b] + cnt[ t] ) % mod;
}
}
}
return ;
}
int main ( ) {
cin >> n >> m;
g. resize ( n + 10 ) ;
for ( int i = 0 ; i < m; ++ i) {
int a, b;
cin >> a >> b;
g[ a] . emplace_back ( b) ;
g[ b] . emplace_back ( a) ;
}
bfs ( ) ;
for ( int i = 1 ; i <= n; ++ i) {
cout << cnt[ i] << endl;
}
return 0 ;
}
题目4 :383观光
C++代码如下,
# include <iostream>
# include <cstring>
# include <algorithm>
# include <queue>
# include <tuple>
# include <vector>
using namespace std;
typedef tuple< int , int , int > TIII;
const int N = 1010 ;
int dist[ N] [ 2 ] ;
int cnt[ N] [ 2 ] ;
bool st[ N] [ 2 ] ;
int n, m;
int S, F;
vector< vector< pair< int , int >> > g;
void dijkstra ( ) {
memset ( dist, 0x3f , sizeof dist) ;
memset ( cnt, 0 , sizeof cnt) ;
memset ( st, 0 , sizeof st) ;
priority_queue< TIII, vector< TIII> , greater< TIII>> hp;
dist[ S] [ 0 ] = 0 , cnt[ S] [ 0 ] = 1 ;
hp. push ( { 0 , S, 0 } ) ;
while ( ! hp. empty ( ) ) {
int distance, node, type;
tie ( distance, node, type) = hp. top ( ) ;
hp. pop ( ) ;
int count = cnt[ node] [ type] ;
if ( st[ node] [ type] ) continue ;
st[ node] [ type] = true ;
for ( auto [ b, w] : g[ node] ) {
if ( dist[ b] [ 0 ] > distance + w) {
dist[ b] [ 1 ] = dist[ b] [ 0 ] , cnt[ b] [ 1 ] = cnt[ b] [ 0 ] ;
hp. push ( make_tuple ( dist[ b] [ 1 ] , b, 1 ) ) ;
dist[ b] [ 0 ] = distance + w, cnt[ b] [ 0 ] = count;
hp. push ( make_tuple ( dist[ b] [ 0 ] , b, 0 ) ) ;
} else if ( dist[ b] [ 0 ] == distance + w) cnt[ b] [ 0 ] += count;
else if