NC25191. biubiubiu 游览哈工程
描述
BiuBiuBiu 是哈尔滨工程大学的一名本科生，在 2016 年他第一次踏入哈尔滨工程大学的大门，他发现学校竟然是传说中的 AAAA 级景区，经过一天的游览，BiuBiuBiu 发现学校一共有 n 个建筑，有一些建筑之间有一些双向联通的道路，BiuBiuBiu 走每条道路的时间都为 1 分钟,而第 i 条道路所需体力为c[i],在 BiuBiuBiu 三年的大学生活中，他一直被一个问题所困扰，现在他想让你帮他解决这个问题。BiuBiuBiu 的寝室在十公寓，每天他都要去 21B 的 573 训练，可是 573 每天开门的时间为 k，所以 BiuBiuBiu 不能在第 k 分钟之前到达 573,但是 BiuBiuBiu 可以在 573 开门前去校园内的其他景点游玩，BiuBiuBiu 的懒惰值为 L，他不想走那些所需体力大于 L 的道路。第一分钟 BiuBiuBiu 在十公寓，每一分钟刚开始 BiuBiuBiu 会在纸上写下自己现在的位置，当然懒惰的 BiuBiuBiu 也可能原地不动，由于 BiuBiuBiu 十分热爱学习，所以他会恰好在第 k 分钟出现在 573 的门口，BiuBiuBiu 想知道他的纸上可能有多少种不同的路径记录。
输入描述
第 一 行 输 入 四 个 整 数 ：n(1<=n<=100),
m(1<=m<=500), k(2<=k<=1e18), L(1<=L<=100)，分别表示校园中的建筑数n，建筑之间的道路数m，BiuBiuBiu可以游玩的时间k以及BiuBiuBiu的懒惰值L。
接下来的一行有n个单词，代表学校中每个景点的名字。
接下来的m行，每行有三个元素，分别表示第i条道路所连接的两个景点的名字以及BiuBiuBiu走第i条道路所需体力值c[i] (1<=c[i]<=1000)。(十公寓的名字为"A10"，573的名字为"573")
输出描述
输出一行表示方案数，由于方案数可能过大，请对100000007取模后进行输出。
示例1
输入:
8 10 4 2 A6 A7 B6 B7 A10 21A 21B 573 A10 A6 1 A10 A7 1 A10 B6 1 A10 B7 1 A6 21A 1 A7 21A 1 B6 21B 1 B7 21B 1 21A 573 1 21B 573 1
输出:
4
示例2
输入:
8 10 4 2 A6 A7 B6 B7 A10 21A 21B 573 A10 A6 1 A10 A7 1 A10 B6 1 A10 B7 1 A6 21A 1 A7 21A 3 B6 21B 1 B7 21B 3 21A 573 1 21B 573 1
输出:
2
C++11(clang++ 3.9) 解法, 执行用时: 194ms, 内存消耗: 864K, 提交时间: 2019-04-21 14:06:05
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int N=(int)104;
const int Mod=(int)100000007;
int n;
struct Matrix {
ll a[N][N];
Matrix() {
memset(a,0,sizeof(a));
}
Matrix operator *(const Matrix &s) const{
Matrix t;
FOR(i,1,n) {
FOR(j,1,n) if(a[i][j]) {
FOR(k,1,n) if(s.a[j][k]) {
t.a[i][k]=(t.a[i][k]+a[i][j]*s.a[j][k])%Mod;
}
}
}
return t;
}
};
map<string,int> Id;
Matrix E;
Matrix f;
int main() {
int m,L;
ll K;
scanf("%d%d%lld%d",&n,&m,&K,&L);
--K;
FOR(i,1,n) {
string s;
cin >> s;
Id[s]=i;
}
int S=Id["A10"];
int T=Id["573"];
FOR(i,1,m) {
string a,b;
cin >> a >> b;
int x=Id[a];
int y=Id[b];
int v;
scanf("%d",&v);
if(x && y && v<=L) {
E.a[x][y]=1;
E.a[y][x]=1;
}
}
FOR(i,1,n) E.a[i][i]=1;
E.a[T][T]=0;
f.a[S][S]=1;
for(; K; K>>=1,E=E*E) {
if(K&1) f=f*E;
}
printf("%lld\n",(f.a[S][T]+Mod)%Mod);
return 0;
}