题意
一张n个点，m条边的有向图，你要从1到n。每条边有一个限制x表示，要使用这条边你必须先经过了x条边。求最短路。
n
,
m
≤
150
,
x
≤
1
e
9
n,m\leq150,x\leq1e9
n,m≤150,x≤1e9
思路
将边排序，然后枚举最终需要使用（而不是可以使用）的边集，首先考虑如何让选中的所有边可行。设
F
[
i
]
F[i]
F[i]表示走到
i
i
i并且恰好解锁当前边是否可行。发现在这条边可用前，可用边集是不变的。于是可以使用上一条加入边集的边的
F
F
F来更新这一次的
F
F
F。这里需要用到矩阵快速幂来加速，并且还要使用bitset优化。把当前的可行图跑一个floyd。再枚举解锁所有选中边的点，计算长度即可。
O
(
m
n
3
/
w
log
(
d
)
)
O(mn^3/w\log(d))
O(mn3/wlog(d)),CF 4s足够通过本题。
#include <bits/stdc++.h>
using namespace std
;
const int N
= 160, inf
= 1e9 + N
;
int n
, m
;
bool a
[N
][N
], b
[N
][N
], lasb
[N
][N
];
int f
[N
][N
];
pair
<int, pair
<int,int> > edge
[N
];
int ans
= inf
;
bitset
<N
> ar
[N
], br
[N
];
void mult(const bool a
[N
][N
], const bool b
[N
][N
], bool c
[N
][N
]) {
for(int i
= 1; i
<= n
; i
++) {
ar
[i
].reset();
for(int j
= 1; j
<= n
; j
++) {
ar
[i
][j
] = a
[i
][j
];
}
}
for(int j
= 1; j
<= n
; j
++) {
br
[j
].reset();
for(int i
= 1; i
<= n
; i
++) {
br
[j
][i
] = b
[i
][j
];
}
}
for(int i
= 1; i
<= n
; i
++) {
for(int j
= 1; j
<= n
; j
++) {
c
[i
][j
] = (ar
[i
] & br
[j
]).any();
}
}
}
void ksm(const bool a
[N
][N
], int y
, bool c
[N
][N
]) {
static bool f
[N
][N
];
memcpy(f
, a
, sizeof f
);
for(; y
; y
>>=1) {
if (y
& 1) mult(c
, f
, c
);
mult(f
, f
, f
);
}
}
int main() {
freopen("d.in","r",stdin);
cin
>>n
>>m
;
for(int i
= 1; i
<= m
; i
++) {
int u
, v
, d
; scanf("%d %d %d",&u
,&v
,&d
);
edge
[i
] = make_pair(d
, make_pair(u
, v
));
}
sort(edge
+ 1, edge
+ 1 + m
);
b
[1][1] = 1;
for(int e
= 1; e
<= m
; e
++) {
ksm(a
, edge
[e
].first
- edge
[e
- 1].first
, b
);
a
[edge
[e
].second
.first
][edge
[e
].second
.second
] = 1;
for(int i
= 1; i
<= n
; i
++) {
for(int j
= 1; j
<= n
; j
++) if (a
[i
][j
]) {
f
[i
][j
] = 1;
} else f
[i
][j
] = inf
;
}
for(int k
= 1; k
<= n
; k
++) {
for(int i
= 1; i
<= n
; i
++) if (i
!= k
) {
for(int j
= 1; j
<= n
; j
++) if (i
!= j
&& j
!= k
) {
f
[i
][j
] = min(f
[i
][j
], f
[i
][k
] + f
[k
][j
]);
}
}
}
for(int i
= 1; i
<= n
; i
++) if (b
[1][i
]) {
ans
= min(ans
, edge
[e
].first
+ f
[i
][n
]);
}
}
if (ans
== inf
) {
printf("Impossible\n");
} else printf("%d\n", ans
);
}
