老六本六-徐梓恒 • 1年前
using namespace std; int main (){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
vector<int> t(n);
for(int i=0;i<n;i++){
cin>>t[i];
}
vector<vector<int> > f(n,vector<int>(n,INF));
for(int i=0;i<n;i++)f[i][i]=0;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
f[x][y]=z;
f[y][x]=z;
}
int q;
cin>>q;
int k=0;
while(q--){
int x,y,z;
cin>>x>>y>>z;
for(;t[k]<=z&&k<t.size();k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
cout<<(f[x][y]==INF||t[x]>z||t[y]>z?-1:f[x][y])<<"\n";
} return 0; }
评论:
这样写
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
const int maxn = 205;
const int inf = 0x3f3f3f3f;
typedef std::pair<int, int> PII;
int map[maxn][maxn];
int retime[maxn];
bool cp[maxn];
std::queue<int> ink;
int n, m, q;
void Floyd(int t);
int main(void) {
memset(map, 0x3f, sizeof(map));
std::cin >> n >> m;
for (int i = 0; i < n; i++)
std::cin >> retime[i];
for (int i = 1, a, b, c; i <= m; i++) {
std::cin >> a >> b >> c;
map[a][b] = c;
map[b][a] = c;
}
std::cin >> q;
while (q--) {
int x, y, t;
std::cin >> x >> y >> t;
if (retime[y] > t || retime[x] > t) {
std::printf("-1\n");
continue;
}
for (int i = 0; i < n; i++)
if (!cp[i] && retime[i] <= t) {
cp[i] = true;
ink.push(i);
}
while (!ink.empty()) {
Floyd(ink.front());
ink.pop();
}
if (map[x][y] >= inf / 2)
std::printf("-1\n");
else
std::printf("%d\n", map[x][y]);
}
return 0;
}
void Floyd(int k) {
for (int i = 0; i < n; i++)
for (int u = 0; u < n; u++)
map[i][u] = std::min(map[i][u], map[i][k] + map[k][u]);
return;
}
请先登录，才能进行评论