有一张 \(n\) 个点 \(m\) 条边的无向图，第 \(i\) 条边开通的条件是你已经走过了 \(d_i\) 条边，问 \(1\to n\) 至少需要走多少条边，或输出无解。\(n\le m\le 150,\,0\le d_i\le 10^9\)。
首先有一个 simple 的想法就是枚举路径上的 \(d\) 最大的边，然后先用比该边 \(d\) 小的边满足要求地走 \(d_i\) 步，然后再用 \(d\) 小于等于该边的边走到终点。
我们考虑将边从大到小排序，首先要算出前 \(d_i\) 步能到哪儿，这不难用矩乘，然后是走用小于等于 \(d_i\) 的边走到终点，这一个 bfs 即可解决。
cpp
#define _CRT_SECURE_NO_WARNINGS
#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
inline char gc() {
static const int L = 233333;
static char sxd[L], *sss = sxd, *ttt = sxd;
if (sss == ttt) {
ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
if (sss == ttt) {
return EOF;
}
}
return *sss++;
}
#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
inline char readalpha() {
char dd;
for (; !isalpha(c); dd);
return c;
}
inline char readchar() {
char dd;
for (; c == ' '; dd);
return c;
}
template <class T>
inline bool read(T& x) {
bool flg = false;
char dd;
x = 0;
for (; !isdigit(c); dd) {
if (c == '-') {
flg = true;
} else if(c == EOF) {
return false;
}
}
for (; isdigit(c); dd) {
x = (x * 10) + (c ^ 48);
}
if (flg) {
x = -x;
}
return true;
}
#undef dd
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x < 10) {
putchar(x | 48);
return;
}
write(x / 10);
putchar((x % 10) | 48);
}
template <class T>
inline void writesp(T x) {
write(x);
putchar(' ');
}
template <class T>
inline void writeln(T x) {
write(x);
puts("");
}
#define lowbit(x) (x & -x)
namespace dfcmd {
const int maxn = 155;
const int inf = 0x3f3f3f3f;
int n, m;
struct Matrix {
bitset<maxn> mt[maxn];
Matrix () {
for (int i = 0; i < maxn; ++i) {
mt[i].reset();
}
}
inline void init() {
for (int i = 1; i <= n; ++i) {
mt[i][i] = 1;
}
}
friend Matrix operator * (const Matrix& a, const Matrix& b) {
Matrix ans;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (a.mt[i][j]) {
ans.mt[i] |= b.mt[j];
}
}
}
return ans;
}
};
inline Matrix ksm(Matrix a, int b) {
Matrix ans;
ans.init();
for (; b; b >>= 1, a = a * a) {
// cout << "aruba" << endl;
if (b & 1) {
ans = ans * a;
}
}
/*
cout << endl;
cout << "ans = " << endl;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cout << ans.mt[i][j] << ' ';
}
cout << endl;
}
cout << endl;
*/
return ans;
}
Matrix mt;
struct Edge {
int from, to, dist;
friend bool operator < (const Edge& a, const Edge& b) {
return a.dist < b.dist;
}
} e[maxn];
int mp[maxn][maxn];
int dist[maxn][maxn];
int vis[maxn];
inline void bfs(int from) {
queue<int> q;
dist[from][from] = 0;
memset(vis, 0, sizeof(vis));
vis[from] = 1;
q.push(from);
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = 1; i <= n; ++i) {
if (!vis[i] && mp[now][i]) {
dist[from][i] = dist[from][now] + 1;
vis[i] = 1;
q.push(i);
}
}
}
}
int Main() {
read(n), read(m);
for (int i = 1; i <= m; ++i) {
read(e[i].from), read(e[i].to), read(e[i].dist);
}
sort(e + 1, e + m + 1);
int Ans = inf;
int now = 0;
Matrix ans;
ans.init();
for (int i = 1; i <= m; ) {
ans = ans * ksm(mt, e[i].dist - e[now].dist);
/*
cout << endl;
cout << "dist = " << e[i].dist << endl;
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
cout << ans.mt[j][k] << ' ';
}
cout << endl;
}
cout << endl;
*/
now = i;
while (i <= m && e[now].dist == e[i].dist) {
mt.mt[e[i].from][e[i].to] = 1;
mp[e[i].from][e[i].to] = 1;
i++;
}
memset(dist, 0x3f, sizeof(dist));
for (int j = 1; j <= n; ++j) {
if (ans.mt[1][j]) {
bfs(j);
Ans = min(Ans, e[now].dist + dist[j][n]);
}
}
/*
cout << endl;
cout << "dist = ";
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cout << dist[i][j] << ' ';
}
cout << endl;
}
cout << endl;
*/
}
if (Ans < inf) {
writeln(Ans);
} else {
puts("Impossible");
}
return 0;
}
}
int main() {
return dfcmd::Main();
}