题目链接：https://codeforces.com/gym/101667/attachments
题意：有
p
p
p个人，他们各自在不同的图里面，每个图都有一个终点，现在他们都需要从
1
1
1点同时到达终点，每条边有个边权，每个点也有一个权值，当某个人在该点选择不走时花费为该点点权，问所有人总的最少花费是多少。
解题心得：花费的时间最坏可能是
n
3
n^{3}
n3天，在一个点不动可以看成自环，这样可以直接用
d
p
dp
dp来表示，
d
p
[
i
]
[
j
]
[
k
]
dp[i][j][k]
dp[i][j][k]表示第
i
i
i个人在第
k
k
k天到达
j
j
j点的最少花费是多少，每一天转移一次。
#include <bits/stdc++.h>
using namespace std
;
typedef long long ll
;
const ll maxn
= 1e5+5e4;
const int maxm
= 55;
const ll INF
= 1e17;
ll n
[5], p
, m
[5], End
[5];
ll dp
[5][maxm
][maxn
], sp
[5][maxm
];
vector
<pair
<ll
, ll
> > ve
[5][maxm
];
void init() {
scanf("%lld", &p
);
for(ll i
=1;i
<=p
;i
++) {
scanf("%lld%lld", &n
[i
], &m
[i
]);
for(ll j
=1;j
<=n
[i
];j
++) {
scanf("%lld", &sp
[i
][j
]);
ve
[i
][j
].push_back({j
, sp
[i
][j
]});
}
for(ll j
=1;j
<=m
[i
];j
++) {
ll a
, b
, c
;
scanf("%lld%lld%lld", &a
, &b
, &c
);
ve
[i
][a
].push_back({b
, c
});
}
for(ll j
=0;j
<maxm
;j
++) {
for(ll k
=0;k
<maxn
;k
++)
dp
[i
][j
][k
] = INF
;
}
scanf("%lld", &End
[i
]);
}
}
bool vis
[maxm
];
void DP() {
for(ll z
=1;z
<=p
;z
++) {
queue
<ll
> qu1
, qu2
;
dp
[z
][1][1] = 0;
qu1
.push(1);
for(int t
=1;t
<maxn
;t
++) {
while (!qu1
.empty()) {
ll now
= qu1
.front();
qu1
.pop();
for (ll i
= 0; i
< ve
[z
][now
].size(); i
++) {
ll v
= ve
[z
][now
][i
].first
;
ll va
= ve
[z
][now
][i
].second
;
if (dp
[z
][v
][t
+ 1] > dp
[z
][now
][t
] + va
) {
dp
[z
][v
][t
+ 1] = dp
[z
][now
][t
] + va
;
if (!vis
[v
]) {
vis
[v
] = true
;
qu2
.push(v
);
}
}
}
}
while(!qu2
.empty()) {
qu1
.push(qu2
.front());
vis
[qu2
.front()] = false
;
qu2
.pop();
}
}
}
}
int main() {
init();
DP();
ll Min
= INF
;
for(ll j
=1;j
<maxn
;j
++) {
ll sum
= 0;
for(ll z
=1;z
<=p
;z
++) {
sum
+= dp
[z
][End
[z
]][j
];
}
Min
= min(Min
, sum
);
}
printf("%lld\n", Min
);
}
